Subject: categories: Undirected graphs

From: Robert Pare <[email-masked]>
Date: Wed, 8 Mar 2006 11:07:20 -0400 (AST)

[note from moderator: resent due to faulty From: ]

I've been following the recent posts on undirected graphs
with interest. But I have a question. I think it's being said
that undirected graphs are the same as directed graphs with
involution. (Presheaves on the full subcategory of SET determined
by 1 and 2, or just 2.) Which is nice but what about loops?
The involution might fix a loop or not. So wouldn't we be
getting undirected graphs with two kinds of loops, whole loops
and semiloops? What am I missing?

Bob

---

From: Marco Grandis <[email-masked]>
Date: Fri, 10 Mar 2006 09:07:03 +0100

Dear Bob,

Involutive graphs are what you are saying, of course. If I had to
choose, I would take this as my favoured notion of "undirected
graph", because it is a presheaf topos on a very simple site.

A graph theorist would probably say that an "undirected graph" is
what you are hinting at, which amounts to taking the involutive
graphs where all loops are fixed by the involution (or the ones where
no loop is fixed, except the trivial ones?). Then, he might want to
forget about trivial loops, and allow vertices with no loops.

Being in a category list, another reason of "preferring" the first
notion might be:

- a category has an underlying graph,
- an involutive category has an underlying involutive graph,
- involutive categories where all endomorphisms are fixed by the
involution are rather unnatural; not to mention the ones where no
endomorphism is fixed except the identities.

Of course, there might be reasons in favour of the other choices, or
of considering different choices at a time. Life is complicated and
mathematics too. Even working in category theory, I think we should
avoid being too "categorical"...

Best regards

Marco

---

From: F W Lawvere <[email-masked]>
Date: Thu, 9 Mar 2006 09:05:13 -0500 (EST)

Dear all,
  Yes, there are two kinds of loops in the topos of right
actions of the four-element monoid A, where A consists of endomaps of
the two-element set. Consider for example the concrete structure of the
truth-value object in that topos, which is forced to contain a truth-value
called "foray". Rather than as "semi"loops, my colleagues and I usually
think of them as one-lane in the sense that some other edges are really
two lanes, related by the involution operator in the site.

  My old paper "Qualitative distinctions..." tried to make the point that
there are several precise toposes all deserving the rough name of "graph"
or "network" and that each of these precise toposes may have a role to
play. For example, in any given topos, for any given object L, the
category of objects over L, or "L-labelled graphs" (which in practice may
serve as a category of networks) is another topos of "graphs".

  In my experience it is important to consider the whole topos in order to
get good exactness properties but, moreover, because the truth-value
object and other specific objects which may seem rather far from an
initial prejudice about what one wants the objects to mean, nonetheless
turn out in a systematic theory to play a key role in representing
concepts directly related to the original particular subject matter.
A simple example is the representability of gender and moitie in the topos
of kinship systems. This example is treated briefly in Conceptual
Mathematics and in more detail, (again actually involving several related
toposes rather than a single choice) in "Kinship and mathematical
categories".

   Bill

************************************************************
F. William Lawvere
Mathematics Department, State University of New York
244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA
Tel. 716-645-6284
HOMEPAGE:  http://www.acsu.buffalo.edu/~wlawvere
************************************************************

---

From: Sebastiano Vigna <[email-masked]>
Date: Thu, 09 Mar 2006 07:56:00 +0100

> and semiloops? What am I missing?

Yes, you'll get two kind of loops. This explains why in topological
graph theory books sometimes you'll find a remark like "we will count
loops once" or "we will count loops twice" (in the first case, sometimes
loops are depicted as segments going out of vertices with a dashed
ending). The problem is that the standard representation for undirected
graphs (subsets of unordered pairs) fails to distinguish between the two
kind of loops. The presheaf representation makes this distinction
clear.

In most cases you can forget about this problem, but when studying
covering the difference is huge: a loop fixed by the involution is
covered by an edge, whereas a pair of loops exchanged by the involution
are covered by a line. We discussed this issue at some length in our
paper "Fibrations of graphs" (Discrete Math., 2002).

Ciao,

						seba

---

From: Vaughan Pratt <[email-masked]>
Date: Fri, 10 Mar 2006 09:17:57 -0800

Sebastiano Vigna wrote on 3/8/06:
>  The problem is that the standard representation for undirected

I wouldn't call this a "failure" of the set-of-unordered-pairs notion of
undirected graph, which should be understood in 2-enriched (2 = 0->1)
terms rather than Set-enriched.  In my March 1 post I distinguished the
"set-enriched" or presheaf graph categories Set-DGraph and Set-UGraph
from the "2-enriched" graph categories 2-DGraph and 2-UGraph ("homsets"
of edges are either 0 or 1, i.e. empty or singleton), pointing out that
2-UGraph was a full subcategory of 2-DGraph but Set-UGraph was not a
full subcategory of 2-DGraph, via the same mechanism that creates two
kinds of loops in Set-UGraph.

There is only one kind of loop in 2-UGraph, which category theory is
faithful to when this kind of undirected graph is properly described in
categorical language.  One description would be as the full subcategory
of Set-UGraph (= Set^M^op for M the monoid Set(2,2)) induced by the
evident functor Nonempty:Set->2 collapsing nonempty homsets to
singletons; it would be nice if 2-UGraph arose more naturally, e.g. as
some sort of 2-enriched presheaf category, though I don't see how.

Vaughan Pratt

---

From: Vaughan Pratt <[email-masked]>
Date: Sat, 11 Mar 2006 20:10:16 -0800

My definition of 2-UGraph (undirected graphs with at most one edge from
any given vertex to another) as "the full subcategory of Set-UGraph (=
Set^M^op for M the monoid Set(2,2)) induced by the evident functor
Nonempty:Set->2 collapsing nonempty homsets to singletons" was an
attempt to say "2-UGraph is a retract of Set-UGraph" with both too few
words and too many.

2-UGraph is the full subcategory of Set-UGraph consisting of graphs with
at most one edge per "homset", and at the same time the quotient of
Set-UGraph arising from identifying all members of each homset of each
graph.  I.e. a retract.

This is something of an eye-opener for me as I have for decades thought
of the undirected graph (of the one-edge-per-homset kind) as the
algebraically impoverished cousin of the directed graph.  I am tickled
pink to find it arising as a retract of a presheaf category, and
moreover without either of the two quirks that have been pointed out for
the more general undirected graphs allowing multiple edges per homset
(Set-UGraph has two types of distinguished loop, and does not embed in
Set-DGraph).

Vaughan Pratt

---

From: F W Lawvere <[email-masked]>
Date: Sun, 12 Mar 2006 19:51:36 -0500 (EST)

Dear Vaughan,

    I hope you will also like the following remark:
Inside any presheaf or other topos there is a canonical subcategory
which is an adjoint retract with the adjoint preserving finite products
(but not equalizers). This category is therefore cartesian closed in the
obvious way, but its special property is that any two maps from X to Y are
distinguished by a map from 1 to X. It is never a topos and its exactness
properties are rather bad, but it does recapture classical restrictions in
many cases. For example, within the Boolean algebra classifier
(=presheaves on the category of non-empty finite sets) this canonical
subcategory is the category of all classical simplicial complexes, a
"higher dimensional" version of your remark about undirected graphs.

    Let me take this opportunity to make another remark about undirected
graphs. They are treated on pages 176 - 180 in the book by Bob Rosebrugh
and me where in particular the two kinds of loops are clearly pointed out.
But I like Steve Schanuel's proposal of a way of picturing these objects:
there is a "geometric realization" functor from undirected graphs to
topological spaces which preserves all colimits ("gluing") (but not finite
limits), namely the Kan extension of the covariant inclusion of the monoid
into topological spaces which interprets the involution as  1-t on the
unit interval. Since the one-lane "loop" is the coequalizer of two maps
from I to I in the graph topos, the same coequalizer statement remains
true for the geometric realizations. Therefore, the resulting picture of
the one-lane loop is as a cul-de-sac, with one starting point, a
parameterization which goes until t=1/2, then returns to the starting
point, without encountering any other points. For example, the truth
value "foray" can be pictured this way. This flattened loop picture
not only has the foregoing rigorous justification but should make
visualizing the objects less nerve-wracking. Of course, the two-lane loops
are now pictured simply as loops, parameterized in two canonical ways
by the unit interval.

Bill