From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/3083 Path: news.gmane.org!not-for-mail From: Sebastiano Vigna Newsgroups: gmane.science.mathematics.categories Subject: Re: Undirected graphs Date: Thu, 09 Mar 2006 07:56:00 +0100 Message-ID: <1141887360.12171.6.camel@localhost.localdomain> References: <20060308150720.9D5D07375B@chase.mathstat.dal.ca> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1241019085 7174 80.91.229.2 (29 Apr 2009 15:31:25 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:31:25 +0000 (UTC) To: categories@mta.ca Original-X-From: rrosebru@mta.ca Fri Mar 10 05:51:04 2006 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 10 Mar 2006 05:51:04 -0400 Original-Received: from Majordom by mailserv.mta.ca with local (Exim 4.52) id 1FHe9b-0001jC-Ek for categories-list@mta.ca; Fri, 10 Mar 2006 05:43:23 -0400 In-Reply-To: <20060308150720.9D5D07375B@chase.mathstat.dal.ca> Original-Sender: cat-dist@mta.ca Precedence: bulk X-Keywords: X-UID: 29 Original-Lines: 29 Xref: news.gmane.org gmane.science.mathematics.categories:3083 Archived-At: On Wed, 2006-03-08 at 11:07 -0400, Robert Pare wrote: > by 1 and 2, or just 2.) Which is nice but what about loops? > The involution might fix a loop or not. So wouldn't we be > getting undirected graphs with two kinds of loops, whole loops > and semiloops? What am I missing? Yes, you'll get two kind of loops. This explains why in topological graph theory books sometimes you'll find a remark like "we will count loops once" or "we will count loops twice" (in the first case, sometimes loops are depicted as segments going out of vertices with a dashed ending). 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. In most cases you can forget about this problem, but when studying covering the difference is huge: a loop fixed by the involution is covered by an edge, whereas a pair of loops exchanged by the involution are covered by a line. We discussed this issue at some length in our paper "Fibrations of graphs" (Discrete Math., 2002). Ciao, seba