Undirected graphs citation

Undirected graphs citation

[Vaughan Pratt]

What would be an early reference for the representation of undirected
graphs (of the set-enriched rather than {0,1}-enriched kind) as
presheaves on the full subcategory 1 and 2 of Set?

Vaughan Pratt

Re: Undirected graphs citation

[wlawvere]

Bob Rosebrugh and I use that point of view explicitly in our book
Set for Mathematics, but it is also in my paper "Qualitative
distinctions..."graphs".  Many of the more precise papers on
combinatorics carefully describe each piece of the graph structure
without noting that  this amounts to a presentation of  the monoid
of endomaps of the 2 element set (which of course suffices).

A similar lacuna of explicitness occurs in many papers on Galois
theory where pregroupoids are an intermediate step ; the
description of  the pregroupoid concept is really just a presentation
of the monoid of endomaps of the 4-element set.  (A right action of
that monoid is a groupoid if it satisfies the evident  pullback
condition on the action of the idempotents, the associative law
being a case of the well-definedness of  higher composition.)



Quoting Vaughan Pratt <pratt@cs.stanford.edu>:

> What would be an early reference for the representation of
> undirected
> graphs (of the set-enriched rather than {0,1}-enriched kind) as
> presheaves on the full subcategory 1 and 2 of Set?
>
> Vaughan Pratt
>
>
>
>

Re: Undirected graphs citation

[Marco Grandis]

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

Re: Undirected graphs citation

[wlawvere]

Why the "curious" omission of this topos from most discussions of combinatorial topology ?

The introduction of ordered simplices by Eilenberg 60 years ago is usually explained in
subjective terms like the annoying extra degeneracies that had to be eliminated in the
previous theory . However there is a objective requirement clearly pointed out by Gabriel &
Zisman. (They spoke of Kelley spaces but that was a mistake due to Kelley's excellent
exposition of the k-spaces of Hurewicz). The requirement is that geometric realization r (left
adjoint to "singular" s) be left exact, so that products and equations on fleshed out spaces
can be the reflection simply of the same operations on the combinatorial models.

If we construe spaces as Johnstone did (or in many other possible ways) as forming
themselves a topos, the the above requirement is simply that r/s constitute a geometric
morphism of toposes. To understand the qualitative distinction between the possible
codomain combinatorial toposes, it is very helpful to note their role as CLASSIFYING toposes.
That role is not always easy  to grasp in the specific if one starts with primitives and axioms
for a first order theory, tries to present the corresponding Lindenbaum category, then takes
sheaves on that, etc. Fortunately in some cases one can bypass that presentation process
because the resulting small category is already well known.

Preheaves on the category of non-empty finite posets clearly classify arbitrary non-trivial
distributive lattices in any Grothendieck topos. In other words an s/r teory  can be based on
an "interval" object in spaces that has a DL structure. If we want that to factor through the
subtopos of simplicial sets, we note that the latter is the classifier for those special DLs that
are totally ordered, which translates geometrically to a condition on an interval that the
square is a union of two triangles; since "union" depends on the topology of space, that
condition is often not true for DLs that  at first glance look like intervals.

There are other relevant subtoposes (ie positive classes of DLs) for example those for which
the canonical map from the generic one I to the truth-object is actually a homomorphism
with respect to both lattice operations.

But the presheaves on non-empty finite sets is the subtopos that classifies Boolean algebras.
The generic BA is the obvious one. It does not really describe well its relation to the total
orderings to call it the "synmmetric version". As the one contains all small categories, this
one analogously contains all groupoids. It can still receive an r/s pair as required if only a
space with a BA structure is used as the "interval". The natural choice for that is the in finite
dimensional sphere, which indeed has a continuous BA structure that contains the usual
interval as a subDL. If only this had been known 60 years ago, we could have done without
the simplicial sets, for this singular theory reads to the same homotopy category.  Note that
any Grothendieck topos (including ss!) has a canonical BA object, hence enjoys a canonical
r/s theory valued here.




Quoting Marco Grandis <grandis@dima.unige.it>:

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

Re: Undirected graphs citation

[Clemens.BERGER]

wlawvere@buffalo.edu wrote:

>Why the "curious" omission of this topos from most discussions of combinatorial topology ?
>
>The introduction of ordered simplices by Eilenberg 60 years ago is usually explained in
>subjective terms like the annoying extra degeneracies that had to be eliminated in the
>previous theory . However there is a objective requirement clearly pointed out by Gabriel &
>Zisman. (They spoke of Kelley spaces but that was a mistake due to Kelley's excellent
>exposition of the k-spaces of Hurewicz). The requirement is that geometric realization r (left
>adjoint to "singular" s) be left exact, so that products and equations on fleshed out spaces
>can be the reflection simply of the same operations on the combinatorial models.
>
>If we construe spaces as Johnstone did (or in many other possible ways) as forming
>themselves a topos, the the above requirement is simply that r/s constitute a geometric
>morphism of toposes. To understand the qualitative distinction between the possible
>codomain combinatorial toposes, it is very helpful to note their role as CLASSIFYING toposes.
>That role is not always easy  to grasp in the specific if one starts with primitives and axioms
>for a first order theory, tries to present the corresponding Lindenbaum category, then takes
>sheaves on that, etc. Fortunately in some cases one can bypass that presentation process
>because the resulting small category is already well known.
>
>Preheaves on the category of non-empty finite posets clearly classify arbitrary non-trivial
>distributive lattices in any Grothendieck topos. In other words an s/r teory  can be based on
>an "interval" object in spaces that has a DL structure. If we want that to factor through the
>subtopos of simplicial sets, we note that the latter is the classifier for those special DLs that
>are totally ordered, which translates geometrically to a condition on an interval that the
>square is a union of two triangles; since "union" depends on the topology of space, that
>condition is often not true for DLs that  at first glance look like intervals.
>
>There are other relevant subtoposes (ie positive classes of DLs) for example those for which
>the canonical map from the generic one I to the truth-object is actually a homomorphism
>with respect to both lattice operations.
>
>But the presheaves on non-empty finite sets is the subtopos that classifies Boolean algebras.
>The generic BA is the obvious one. It does not really describe well its relation to the total
>orderings to call it the "synmmetric version". As the one contains all small categories, this
>one analogously contains all groupoids. It can still receive an r/s pair as required if only a
>space with a BA structure is used as the "interval". The natural choice for that is the in finite
>dimensional sphere, which indeed has a continuous BA structure that contains the usual
>interval as a subDL. If only this had been known 60 years ago, we could have done without
>the simplicial sets, for this singular theory reads to the same homotopy category.  Note that
>any Grothendieck topos (including ss!) has a canonical BA object, hence enjoys a canonical
>r/s theory valued here.
>
>Quoting Marco Grandis <grandis@dima.unige.it>:
>
>>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
>
A comment on combinatorial models for spaces : there is the notion of a
CW-poset (due to Bjoerner) which is a poset that can be identified with
the poset of cells of a regular CW-complex; those posets have very
special properties, but from a homotopy point of view, every space is
weakly homotopy equivalent to a regular CW-complex, so every space has a
``CW-poset-model''. Taking the nerve of this poset yields a
``simplicial-set-model'' of the same space; geometrically, the passage
from the poset to its nerve corresponds to barycentric subdivision. Now,
there is an old paper by Daniel Kan (Amer. J. Math. 79 (1957) 449-476,
section 10), where he shows that the barycentric subdivision of a
simplicial set actually has the structure of a symmetric simplicial set.
So, to some extent, symmetric simplicial sets are doubly subdivided
regular CW-complexes. What I wanted to point out is that in the
progression CW-poset->simplicial set->symmetric simplicial set, the
combinatorial information about the space is not increasing, but rather
decreasing, which is one possible argument in favour of simplicial sets
versus symmetric simplicial sets. Another argument for the category of
simplicial sets is that it is a topos which contains the category of
small categories as a full reflective monoidal subcategory. A third
argument is the ubiquitous occurence of simplicial cotriple resolutions.

In his pursuit of stacks, Grothendieck raises the question of what is
the structure on a small category A, which ensures that the presheaf
topos A^ may be endowed with a homotopy theory equivalent to the
homotopy theory of spaces (such a category is called a test-category) or
with the homotopy theory of spaces above a given space (such a category
is called a local-test-category). In the presence of an r/s adjunction
like in Lavwere's message above, the criteria of being local-test or
test are easily spelled out:

A is local-test iff for each object a of A, the projection A[a]\times
\Omega_A\to A[a] realises to a weak equivalence, where \Omega_A is the
subobject classifier of A^ and A[a] is the presheaf represented by a.

A is test iff A is local-test and the nerve of A is weakly contractible.

With best regards,

                       Clemens Berger.

Re: Undirected graphs citation

[Vaughan Pratt]

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
 >