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