Re: relations on graphs

[Vaughan Pratt <pratt@cs.stanford.edu>]

> The category of directed graphs is certainly such a category, being
> regular. The category of graphs is not a topos, I believe, but might
> still be regular.

Suitably defined the category of undirected graphs is indeed a topos.
As came up a year ago on this list (thread beginning with my 2/27/06
inquiry about the history of the presheaf category of undirected
graphs), undirected or symmetric graphs can be defined as M-sets for the
monoid M = Set(2,2), endomorphisms of the doubleton in Set, aka the four
unary Boolean operations.  Of the latter, x and not-x together denote
the two directions of edge x while 0(x) and 1(x) denote its two vertices
(as self-loops).

One might imagine some sort of asymmetry between x and not-x that makes
x the primary direction, but x and not-x always travel together as a
group (quite literally: S_2) under graph homomorphism and their
inseparability justifies the view of the two as forming a single
undirected edge having two directed names, x and not-x.

The singleton splits 0 and 1 to make those self-loops vertices in their
own right, so by Morita equivalence the full subcategory of Set with
objects the positive cardinals up to 2 canonically represents the same
presheaf category up to equivalence.

Dusko Pavlovic, "A categorical setting for the 4-color theorem," JPAA
102, 1, 75--88 (1995), organizes undirected graphs as the above topos.
Section 10.3 (pp. 176--180) of Lawvere and Rosebrugh, Sets for
Mathematics, CUP 2003, develops this topos in more detail, pointing out
the two distinguished loops, an idiosyncrasy of this representation of
undirected graphs.

All this lifts readily to the topos of higher dimensional graphs:
simplicial sets in the directed case, symmetric simplicial sets in the
undirected.  Marco Grandis, in Finite sets and symmetric simplicial
sets, Theory Appl. Categ. 8 (2001), No. 8, 244-252, identified the
presheaves on FinSet with the undirected or symmetric simplicial sets,
which as Clemens Berger pointed out had been encountered much earlier in
another guise by Daniel Kan (Amer. J. Math. 79 (1957) 449-476 as the
barycentric subdivision of a simplicial set.

Vaughan