From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/3087 Path: news.gmane.org!not-for-mail From: F W Lawvere Newsgroups: gmane.science.mathematics.categories Subject: Re: Undirected graphs Date: Sun, 12 Mar 2006 19:51:36 -0500 (EST) Message-ID: References: <44139F28.7070608@cs.stanford.edu> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Trace: ger.gmane.org 1241019087 7186 80.91.229.2 (29 Apr 2009 15:31:27 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:31:27 +0000 (UTC) To: categories@mta.ca Original-X-From: rrosebru@mta.ca Mon Mar 13 01:05:27 2006 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 13 Mar 2006 01:05:27 -0400 Original-Received: from Majordom by mailserv.mta.ca with local (Exim 4.52) id 1FIfAn-0001eG-Vn for categories-list@mta.ca; Mon, 13 Mar 2006 01:00:50 -0400 In-Reply-To: <44139F28.7070608@cs.stanford.edu> Original-Sender: cat-dist@mta.ca Precedence: bulk X-Keywords: X-UID: 33 Original-Lines: 71 Xref: news.gmane.org gmane.science.mathematics.categories:3087 Archived-At: 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