Undirected graphs

Undirected graphs

[Robert Pare]

[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

Re: Undirected graphs

[Sebastiano Vigna]

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

Re: Undirected graphs

[F W Lawvere]

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
>
>
>
>

Re: Undirected graphs

[Marco Grandis]

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
>
>
>

Re: Undirected graphs

[Vaughan Pratt]

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

Re: Undirected graphs

[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

Re: Undirected graphs

[F W Lawvere]

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

Re: Undirected graphs

[Chris Wensley]

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

Re: Undirected graphs

[Dr. Cyrus F Nourani]

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--