The n-Category Café

This work seems to point to a bridge between the two cultures of mathematics. To see MacLane’s name appearing under Lovász’s in the bibliography of the paper by Koslov you mention is a sign.

Interesting stuff!

A simplicial complex is somewhat different from a simplicial set, but they’re closely related, so perhaps you won’t mind me talking about the latter instead of the former.

The word graph means many different things. A directed graph where every vertex $x$ has a chosen ‘identity’ edge from $x$ to itself is an example of a simplicial set. An undirected graph without loops is an example of a simplicial complex.

The category of simplicial sets is very nice: in particular, it’s cartesian closed, so given simplicial sets $X$ and $Y$ there’s a simplicial set $hom(X,Y)$, the ‘internal hom’.

So, if you allow me to work with directed graphs with identity edges, say $X$ and $Y$, and think of them as simplicial sets, there’s a very nice way to make $hom(X,Y)$ into a simplicial set. The vertices of $hom(X,Y)$ are the hopefully obvious structure-preserving maps from $X$ to $Y$. The edges of $hom(X,Y)$ are ‘homotopies’ between such maps — but only ‘directed’ homotopies, I guess. And so on. It’s all very nice.

I don’t know if the category of simplicial complexes is cartesian closed; I’d be mildly shocked if it were.

John wrote:

So, if you allow me to work with directed graphs with identity edges,

Urs wrote:

Unfortunately, I cannot allow you to do that! :-)

Hmm, so maybe we really need to work with undirected graphs. Can these graphs have loops, or more than one edge between vertices?

If not, we’re in business: then these graphs are just simplicial complexes where the highest dimension of a simplex is 1. This allows us to define a simplicial complex of maps between our graphs, since…

John wrote:

I don’t know if the category of simplicial complexes is cartesian closed; I’d be mildly shocked if it were.

but then Todd wrote:

It is.

I’m mildly shocked!

If Grandis’ construction works the way I’m guessing, we can really take two graphs $X$ and $Y$ — that is, simplicial complexes where the highest dimension of a simplex is 1 — and see that $n$-simplices in $hom(X,Y)$ are a simplicial way of describing homotopies between homotopies between… maps from $X$ to $Y$.

In other words, if we think of the simplicial complex $hom(X,Y)$ as a topological space, it’s homotopy equivalent to the space of continuous maps from $X$ to $Y$, where we regard these graphs as spaces too.

Suppose this is true. The next question is: how interesting can this space $hom(X,Y)$ be? The graphs $X$ and $Y$ can be any space with homotopy groups $\pi_n$ vanishing for $n \gt 1$. Given this, what’s the maximum possible homotopy dimension of $hom(X,Y)$? That is, what’s the highest $n$ for which the homotopy group $\pi_n(hom(X,Y))$ can be nonzero?

I’ll guess the answer is just $n = 1$. If it’s higher, I’ll be mildly shocked.

The reason this matters is that Urs suggested there’s an interesting $n$-category of graphs lurking around here. The approach I’m describing makes graphs into a category enriched over simplicial complexes. But since simplicial complexes are a model for homotopy types, we get an $(\infty,1)$-category of graphs: that is, an $\infty$-category where all $j$-morphisms are invertible for $j \gt 1$.

However, it’s quite possible that this is ‘overkill’. If the maximum homotopy dimension of $hom(X,Y)$ is $n$, we essentially have just an $(n+1,1)$-category: an $(n+1$-category where all $j$-morphisms are invertible for $j \gt 1$.

And, if $n = 1$, we basically just have 2-category where all 2-morphisms are invertible.

My reason for guessing that the maximum homotopy dimension of $hom(X,Y)$ for graphs $X$ and $Y$ is just 1 comes from the case where $X$ and $Y$ are homotopy equivalent to circles. In this case $hom(X,Y)$ is homotopy equivalent to $hom(S^1,S^1)$, which I’m betting is homotopy equivalent to a disjoint union of circles!

(If I were really pretending to be a homotopy theorist, I’d just say “is” instead of constantly saying “is homotopy equivalent to”.)

Tom asked about the meaning of ‘cell complex’.

Some people may use ‘cell complex’ loosely to mean CW complex, piecewise-linear CW complex or various other things. I may have been guilty of this myself, in my youth.

But, homotopy theorists like to make the category of topological spaces into a model category where the cofibrations are ‘relative cell complexes’, and this gives the term ‘cell complex’ a very precise definition, which I now support.

Roughly speaking, a map of spaces

$$X \to Y$$

is a relative cell complex if $Y$ is built from $X$ by repeatedly attaching finite-dimensional balls along their boundaries… where ‘repeatedly’ means we get to use transfinite induction. If $X$ is empty, we then say $Y$ is a cell complex.

So, the cell complexes defined this way are the cofibrant objects in $Top$!

A cell complex is a CW complex if the cells are attached in order of increasing dimension.

If you want more precision, try page 30 here:

• Mark Hovey, Model Categories, AMS, Providence, Rhode Island, 1999.

for a general definition of ‘relative $I$-cell complex’, and then page 51 for what this amounts to in the case of topological spaces.

Since cofibrant objects are important, and CW complexes aren’t quite general enough to be the cofibrant objects in $Top$, I think using the word ‘cell complex’ for the necessary slight generalization is a good idea.

Just for the record, I thought I’d point out that all the graphs in the Babson-Kozlov theory are un-oriented, meaning that if there’s an edge from v to w, there’s a corresponding edge from w to v. And most of the time people just think of this as a single undirected edge.

(Small technical comment on the nice opening post: it is of course correct to write

If the graph is the dual of a triangulation drawn on a plane, the answer is given by the famous four color theorem to be χ(G)=4.

yet the usual way of stating the Four Color Theorem has another antecedent, namely ‘If the graph is any loopless planar countable multigraph’.

Yes, usually, proofs of the FCT make some reduction to triangulations, but I just would like to point out the obvious: not every planar loopless multigraph is “the dual of a triangulation in the plane”. E.g. the 4-circuit isn’t: the only way to realize the 4-circuit as a dual is as the dual of the dipole graph with four edges.)