Re: Undirected graph citation

[Marco Grandis <grandis@dima.unige.it>]

Undirected versus directed

Going along with the last messages of C Berger and FW Lawvere, I
would like to list the following parallel notions, undirected versus
directed. Of course, it is not a question of saying which is better,
but only of separating them to make things clearer.

---

Undirected:

- symmetric simplicial sets (sss)
- simplicial complexes (classical)
= sets with distinguished subsets
= sss where each simplex is determined by its vertices
- undirected graphs
- groupoids (fundamental groupoids)
- abelian groups (homology groups)
- spaces
- classical metric spaces
- undirected algebraic topology
---

Directed:

- simplicial sets
- "directed simplicial complexes" (not classical)
= sets with distinguished words
= simplicial sets where each simplex is determined by (the family of)
its vertices
- directed graphs
- categories (fundamental categories)
- preordered abelian groups ("directed homology groups")
- "directed spaces" (preordered, locally preordered, etc.)
- generalised metric spaces (Lawvere)
- "directed algebraic topology"
---

Spaces are plainly an undirected structure. Note that their singular
simplicial set already has a natural symmetric structure (by
"permuting vertices" on tetrahedra); there is no need of symmetrising
it and loosing information.

Classical algebraic topology is mostly undirected (since spaces,
groupoids, abelian groups are so), but it has also used directed
structures, like simplicial sets, for undirected purposes: simulating
spaces and computing undirected algebraic structures, like groupoids
and homology groups.
The study of "directed algebraic topology" is quite recent. (There
are some papers on that in my web page, from which one can see the
literature; present applications are concerned with concurrency and
rewriting. But the general aim should be modeling non-reversible
phenomena.)

Finally, I would like to point out - once more - that the term
"simplicial complex" is highly confusing: this notion (as Bill
recalls) is a simplified version of a symmetric simplicial set, while
the corresponding simplified version of a simplicial set is a "set
with distinguished words" (the reflexive cartesian closed subcategory
of "objects determined by their vertices", in the presheaf topos of
simplicial sets). But I have noticed that people can get nervous
about terminology, and it might be better to forget about this last
point.

Marco Grandis