Re: Undirected graphs

[F W Lawvere <wlawvere@buffalo.edu>]

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

 ************************************************************
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
************************************************************
On Sat, 11 Mar 2006, Vaughan Pratt wrote:

> 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