From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/3064 Path: news.gmane.org!not-for-mail From: "Dr. Cyrus F Nourani" Newsgroups: gmane.science.mathematics.categories Subject: Re: Undirected graphs Date: Thu, 02 Mar 2006 13:16:45 -0500 Message-ID: NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1241019074 7107 80.91.229.2 (29 Apr 2009 15:31:14 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:31:14 +0000 (UTC) To: categories@mta.ca Original-X-From: rrosebru@mta.ca Fri Mar 3 14:53:33 2006 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Fri, 03 Mar 2006 14:53:33 -0400 Original-Received: from Majordom by mailserv.mta.ca with local (Exim 4.52) id 1FFFGi-0003rN-GT for categories-list@mta.ca; Fri, 03 Mar 2006 14:44:48 -0400 Content-Disposition: inline Original-Sender: cat-dist@mta.ca Precedence: bulk X-Keywords: X-UID: 10 Original-Lines: 142 Xref: news.gmane.org gmane.science.mathematics.categories:3064 Archived-At: This is very interesting. The enclosed papers were in part=20 indicating that models can be designed with undirected graphs on Hasse diagrams where disenfrachised computing can create=20 models in pieces. Further insights would be great. Cyrus Functors Computing Hasse Diagram Models February 17, 1997, MiniConferece, Maine, April 1997. Functorial Hasse Models=20 SLK 2002, Eurpean Sumer Logic Colloquium, Munster, Germany, July 2002 wwwmath.uni-muenster.de/LC2002/presentedbytitle.html > ----- Original Message ----- > From: "Vaughan Pratt" > To: categories@mta.ca > Subject: categories: Re: Undirected graphs citation > Date: Wed, 01 Mar 2006 12:58:14 -0800 >=20 >=20 > Marco Grandis wrote: > > It is the 2-truncation of "symmetric simplicial sets" as presheaves > > on finite cardinals, cf (*). >=20 > Marco, thanks for that, this is really nice. It hadn't occurred to me > to extend undirected graphs to higher dimensions but ... of course! >=20 > 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=3Dn+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. >=20 > 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". >=20 > 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. >=20 > 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. >=20 > 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=3Dn+1 > parameters have as domain the set of n-cells. >=20 > 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. >=20 > 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. >=20 > Unless I've overlooked some subtlety, 2-UGraph does however embed in the > expected way in 2-DGraph, where 2 =3D {0,1} (=3D 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. >=20 > Vaughan Pratt >=20 > Marco Grandis wrote: >=20 > > 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 > > > --=20 _______________________________________________ Search for businesses by name, location, or phone number. -Lycos Yellow Pa= ges http://r.lycos.com/r/yp_emailfooter/http://yellowpages.lycos.com/default.as= p?SRC=3Dlycos10 --_----------=_114132340527320--