This is very interesting. The enclosed papers were in part indicating that models can be designed with undirected graphs on Hasse diagrams where disenfrachised computing can create models in pieces. Further insights would be great. Cyrus Functors Computing Hasse Diagram Models February 17, 1997, MiniConferece, Maine, April 1997. Functorial Hasse Models SLK 2002, Eurpean Sumer Logic Colloquium, Munster, Germany, July 2002 wwwmath.uni-muenster.de/LC2002/presentedbytitle.html
----- Original Message ----- From: "Vaughan Pratt" <pratt@cs.stanford.edu> To: categories@mta.ca Subject: categories: Re: Undirected graphs citation Date: Wed, 01 Mar 2006 12:58:14 -0800
Marco Grandis wrote:
It is the 2-truncation of "symmetric simplicial sets" as presheaves on finite cardinals, cf (*).
Marco, thanks for that, this is really nice. It hadn't occurred to me to extend undirected graphs to higher dimensions but ... of course!
While "symmetric" is technically correct terminology here (and indeed graph theorists often define undirected graphs as the symmetric case of directed graphs), "undirected" conveys the appropriate intuition that the edges and higher-dimensional cells have no specific orientation. Whereas the automorphism group of a directed n-cell is the trivial group, that of an undirected n-cell is S_N where N=n+1, i.e. undirected n-cells are permitted to "flop around" in all N! possible ways. Moreover the group as a whole behaves like a single cell with regard to identification: if one of the N! copies of an undirected edge is identified with a copy of another undirected edge, all copies are identified bijectively, i.e. the two undirected cells are identified.
So without taking issue with Marco's terminology "symmetric" here, since it is correct and natural, I would nevertheless like to suggest that in the context of simplicial complexes, and with ordinary graphs as a precedent, that "undirected" be considered an acceptable synonym for "symmetric".
But that connection leads to another that hadn't previously occurred to me (though again this is unlikely to be news to at least some). This is the question of an appropriate language for the signature of simplicial complexes in general.
Each operation can be named with a lambda-calculus term of the form \xyz.xyzzy, that is, a string of (distinct of course) variables followed by another string of the same variables with repetitions or omissions allowed. Dually to undirected simplicial complexes being a special case of (directed) simplicial complexes, the language for the latter is the special case of that for the former in which the body of the lambda term preserves the order of the formal parameter list; the smallest term thus disallowed is \xy.yx.
In particular s and t (source and target) arise as respectively \xy.x and \xy.y: given an edge, bind x and y to its source and target respectively and return the designated vertex. Similarly \x.xx denotes the distinguished self-loop at a given vertex x (these being reflexive graphs since we allow contraction). The lambda terms with N=n+1 parameters have as domain the set of n-cells.
The one operation that undirected graphs have that is absent in the general directed case is \xy.yx, which names the other member of the group of automorphic copies of an undirected edge. These two copies always travel together (literally as a group), justifying the intuition that the group of both of them constitutes a single edge (or n-cell). For general n these copies of a given cell are named by the linear lambda terms, those with exactly one occurrence of each formal parameter. Any given cell of a graph attaches to the rest of the graph at various points around that cell, but graph homomorphisms cannot disturb those points of attachment or incidence, though it can certainly map the cell to any of the N! isomorphic copies of itself.
It should be pointed out that "undirected graph" as a "special case" of "directed graph" has its syntactic rather than semantic meaning here, in the sense that UGraph (undirected graphs) does not embed in DGraph (directed graphs), at least not in the expected way. Consider a graph with two vertices x,y, two edges from x to y, and two edges from y to x. If a graph homomorphism identifies the two edges from x to y, it need not identify the other two edges in DGraph, but it does need to identify them in UGraph.
Unless I've overlooked some subtlety, 2-UGraph does however embed in the expected way in 2-DGraph, where 2 = {0,1} (= V in enriched parlance) are the possible cardinalities of "homsets", i.e. at most one edge in each direction. This is because the implicit pairing in 2-DGraph perfectly mimics the explicit pairing in 2-UGraph. This would explain why graph theorists, who usually work in 2-DGraph, encounter no ambiguity of the Set-UGraph < Set-DGraph kind when they define an undirected graph as simply a symmetric graph, one with no one-way streets.
Vaughan Pratt
Marco Grandis wrote:
Vaughan Pratt asked about:
undirected graphs ... as presheaves on the full subcategory 1 and 2 of Set?
It is the 2-truncation of "symmetric simplicial sets" as presheaves on finite cardinals, cf (*).
Curiously, symmetric simplicial sets have been rarely considered. Even if simplicial complexes (well-known!) are a symmetric notion and have a natural embedding in symmetric simplicial sets. While simplicial sets are a directed notion, used as an undirected one in classical Algebraic Topology.
(*) M. Grandis, Finite sets and symmetric simplicial sets, Theory Appl. Categ. 8 (2001), No. 8, 244-252.
Marco Grandis
-- _______________________________________________ Search for businesses by name, location, or phone number. -Lycos Yellow Pages http://r.lycos.com/r/yp_emailfooter/http://yellowpages.lycos.com/default.asp... --_----------=_114132340527320--
[note from moderator: resent due to faulty From: ] I've been following the recent posts on undirected graphs with interest. But I have a question. I think it's being said that undirected graphs are the same as directed graphs with involution. (Presheaves on the full subcategory of SET determined 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? Bob
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
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
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
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
Dear all, Yes, there are two kinds of loops in the topos of right actions of the four-element monoid A, where A consists of endomaps of the two-element set. Consider for example the concrete structure of the truth-value object in that topos, which is forced to contain a truth-value called "foray". Rather than as "semi"loops, my colleagues and I usually think of them as one-lane in the sense that some other edges are really two lanes, related by the involution operator in the site. My old paper "Qualitative distinctions..." tried to make the point that there are several precise toposes all deserving the rough name of "graph" or "network" and that each of these precise toposes may have a role to play. For example, in any given topos, for any given object L, the category of objects over L, or "L-labelled graphs" (which in practice may serve as a category of networks) is another topos of "graphs". In my experience it is important to consider the whole topos in order to get good exactness properties but, moreover, because the truth-value object and other specific objects which may seem rather far from an initial prejudice about what one wants the objects to mean, nonetheless turn out in a systematic theory to play a key role in representing concepts directly related to the original particular subject matter. A simple example is the representability of gender and moitie in the topos of kinship systems. This example is treated briefly in Conceptual Mathematics and in more detail, (again actually involving several related toposes rather than a single choice) in "Kinship and mathematical categories". 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 Wed, 8 Mar 2006 cat-dist@mta.ca wrote:
I've been following the recent posts on undirected graphs with interest. But I have a question. I think it's being said that undirected graphs are the same as directed graphs with involution. (Presheaves on the full subcategory of SET determined 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?
Bob
Dear Bob
I've been following the recent posts on undirected graphs with interest. But I have a question. I think it's being said that undirected graphs are the same as directed graphs with involution. (Presheaves on the full subcategory of SET determined by 1 or 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?
There has been some 'work in progress' at Bangor on this very question for the past 8 years. This is intended to present a categorical approach to graph theory to workers in combinatorics, and is not intended for category theorists. The current draft, 06.04, is available at http://www.informatics.bangor.ac.uk/public/mathematics/research/preprints/06... (follow the link 06.04 to 06_04.pdf). We do indeed discuss two types of loop, which we call 'loops' and 'bands'. Ronnie is away today, but may well add his own comment tomorrow. Best wishes, Chris Wensley
Dear Bob, Involutive graphs are what you are saying, of course. If I had to choose, I would take this as my favoured notion of "undirected graph", because it is a presheaf topos on a very simple site. A graph theorist would probably say that an "undirected graph" is what you are hinting at, which amounts to taking the involutive graphs where all loops are fixed by the involution (or the ones where no loop is fixed, except the trivial ones?). Then, he might want to forget about trivial loops, and allow vertices with no loops. Being in a category list, another reason of "preferring" the first notion might be: - a category has an underlying graph, - an involutive category has an underlying involutive graph, - involutive categories where all endomorphisms are fixed by the involution are rather unnatural; not to mention the ones where no endomorphism is fixed except the identities. Of course, there might be reasons in favour of the other choices, or of considering different choices at a time. Life is complicated and mathematics too. Even working in category theory, I think we should avoid being too "categorical"... Best regards Marco On 8 Mar 2006, at 16:07, cat-dist@mta.ca wrote:
I've been following the recent posts on undirected graphs with interest. But I have a question. I think it's being said that undirected graphs are the same as directed graphs with involution. (Presheaves on the full subcategory of SET determined 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?
Bob
participants (7)
-
Chris Wensley -
Dr. Cyrus F Nourani -
F W Lawvere -
Marco Grandis -
Robert Pare -
Sebastiano Vigna -
Vaughan Pratt