From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/3686 Path: news.gmane.org!not-for-mail From: Vaughan Pratt Newsgroups: gmane.science.mathematics.categories Subject: Re: relations on graphs Date: Fri, 09 Mar 2007 09:02:23 -0800 Message-ID: NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1241019455 9779 80.91.229.2 (29 Apr 2009 15:37:35 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:37:35 +0000 (UTC) To: categories@mta.ca Original-X-From: rrosebru@mta.ca Fri Mar 9 14:32:45 2007 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 09 Mar 2007 14:32:45 -0400 Original-Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1HPjq1-00060S-HF for categories-list@mta.ca; Fri, 09 Mar 2007 14:29:09 -0400 Original-Sender: cat-dist@mta.ca Precedence: bulk X-Keywords: X-UID: 40 Original-Lines: 42 Xref: news.gmane.org gmane.science.mathematics.categories:3686 Archived-At: > 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