From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/3085 Path: news.gmane.org!not-for-mail From: Vaughan Pratt Newsgroups: gmane.science.mathematics.categories Subject: Re: Undirected graphs Date: Fri, 10 Mar 2006 09:17:57 -0800 Message-ID: <4411B4C5.2040702@cs.stanford.edu> References: <20060308150720.9D5D07375B@chase.mathstat.dal.ca> <1141887360.12171.6.camel@localhost.localdomain> 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 1241019086 7178 80.91.229.2 (29 Apr 2009 15:31:26 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:31:26 +0000 (UTC) To: categories@mta.ca Original-X-From: rrosebru@mta.ca Fri Mar 10 18:28:22 2006 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 10 Mar 2006 18:28:22 -0400 Original-Received: from Majordom by mailserv.mta.ca with local (Exim 4.52) id 1FHq4Y-0004aA-1G for categories-list@mta.ca; Fri, 10 Mar 2006 18:26:58 -0400 X-Accept-Language: en-us, en In-Reply-To: <1141887360.12171.6.camel@localhost.localdomain> Original-Sender: cat-dist@mta.ca Precedence: bulk X-Keywords: X-UID: 31 Original-Lines: 27 Xref: news.gmane.org gmane.science.mathematics.categories:3085 Archived-At: Sebastiano Vigna wrote on 3/8/06: > 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. 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