Re: Undirected graphs

["Dr. Cyrus F Nourani" <projectm2@lycos.com>]

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?SRC=lycos10


--_----------=_114132340527320--