From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/3086 Path: news.gmane.org!not-for-mail From: Vaughan Pratt Newsgroups: gmane.science.mathematics.categories Subject: Re: Undirected graphs Date: Sat, 11 Mar 2006 20:10:16 -0800 Organization: Stanford University Message-ID: <44139F28.7070608@cs.stanford.edu> References: <20060308150720.9D5D07375B@chase.mathstat.dal.ca> <1141887360.12171.6.camel@localhost.localdomain> <4411B4C5.2040702@cs.stanford.edu> Reply-To: pratt@cs.stanford.edu 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 7182 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 Sun Mar 12 18:48:00 2006 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Sun, 12 Mar 2006 18:48:00 -0400 Original-Received: from Majordom by mailserv.mta.ca with local (Exim 4.52) id 1FIZAV-0004Pf-HV for categories-list@mta.ca; Sun, 12 Mar 2006 18:36:07 -0400 User-Agent: Mozilla Thunderbird 0.9 (Windows/20041103) In-Reply-To: <4411B4C5.2040702@cs.stanford.edu> Original-Sender: cat-dist@mta.ca Precedence: bulk X-Keywords: X-UID: 32 Original-Lines: 24 Xref: news.gmane.org gmane.science.mathematics.categories:3086 Archived-At: 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