Why do wedges of spheres often appear in combinatorics?

Question

Robin Forman writes in "A User's Guide to Discrete Morse Theory":

The reader should not get the impression that the homotopy type of a CW complex is determined by the number of cells of each dimension. This is true only for very few spaces (and the reader might enjoy coming up with some other examples). The fact that wedges of spheres can, in fact, be identified by this numerical data partly explains why the main theorem of many papers in combinatorial topology is that a certain simplicial complex is homotopy equivalent to a wedge of spheres. Namely such complexes are the easiest to recognize. However, that does not explain why so many simplicial complexes that arise in combinatorics are homotopy equivalent to a wedge of spheres. I have often wondered if perhaps there is some deeper explanation for this.

The question is: "Why so many simplicial complexes that arise in combinatorics are homotopy equivalent to a wedge of spheres?"

Answer 1

This is indeed a mystery. I presume the question refers to wedges of spheres of the same dimension, where there's a simple criterion (n-dimensional and (n-1)-connected, for some n). For wedges of spheres of different dimensions I don't know any such criterion. Even when it's known that a complex has the homotopy type of a wedge of n-spheres, it can be difficult to find cycles representing a basis for the homology. Proofs of (n-1)-connectedness are often by induction and hence not really very enlightening, in my experience with complexes arising in combinatorial low-dimensional topology. Ideally such a proof would proceed by showing that after deleting the interiors of some top-dimensional cells, the resulting subcomplex was contractible, hopefully by an explicit contraction. There's even one important case, Harvey's curve complex of a surface, where the complex has higher dimension than the wedge of spheres that it's homotopy equivalent to. It almost seems like a metatheorem in this area that any naturally-defined complex is either contractible or homotopy equivalent to a wedge of spheres. I can't think of any counterexamples, just off the top of my head. Perhaps in other areas the proofs are more enlightening.

Answer 2

One way to approach this question quantitatively is suggested by probability. One can put various measures on the space of all simplicial complexes on $n$ vertices. One perhaps fairly natural measure is to take a random graph and then take the clique complex. This doesn't give us all complexes on $n$ vertices but every complex is homeomorphic to the clique complex of some graph, so we are covering everything up to homeomorphism as $n \to \infty$.

The main point of my paper Topology of random clique complexes is that almost all simplicial complexes arising this way are fairly simple topologically. In particular is shown that for a typical $d$-dimensional clique complex, the homology groups $H_k$ all vanish when $k > \lfloor d/2 \rfloor$ and when $k< d/4$, and that almost all of whatever homology remains is concentrated in the middle dimension $k=\lfloor d/2 \rfloor$.

It is currently an open problem to decide whether the homology is vanishing (or merely small) between $k=d/4$ and $k=d/2$. If one could establish this, then one would be well on the way to showing that almost all flag complexes are homotopy to a wedge of spheres; indeed the last thing to do would be to rule out torsion in middle homology with integer coefficients.

I don't have a good feel for whether either of these things is even true, but I do think that this paper gives good anecdotal evidence that most flag complexes are somewhat simple topologically, and is a step in the direction of answering Forman's question. (This particular measure seems especially natural from the point of view of combinatorics, since so many simplicial complexes arise as order complexes of posets, hence are automatically flag complexes.)

UPDATE:

(1) I showed recently that for every $k \ge 3$, there is a range of edge probability so that the random clique complex (also called random flag complex) is rationally homotopy equivalent to a wedge of $k$-dimensional spheres. In particular all the rational homology is in middle degree. There is only a very small overlap where there is homology in degree $k$ and in degree $k+1$, but in some sense, most of the time there is only homology in one degree. The conjecture that "rationally homotopy equivalent" can be replaced by "homotopy equivalent" is equivalent to showing that with high probability, homology is torsion free.

(2) On the note of torsion in random homology, in joint work with Hoffman and Paquette, we recently showed that for a slightly different model of random simplicial complex, for most of the range where rational homology is vanishing, integer homology is also vanishing.

There are one or two technical issues in applying the method of (2) in the setting of (1) (namely non-monotonicity of homology), but so far it seems like there is reason to believe that the method will go through eventually.

Together, these two recent results suggest that a random flag complex (for a suitable range of edge probability $p$) is homotopy equivalent to wedges of $d$-dimensional spheres. Random flag complexes seem to me like a very natural model for addressing your question probabilistically, since so many complexes in combinatorics are flag complexes, arising as order complexes of posets, etc.

Answer 3

I think it's because we have well-developed techniques with which to prove that this condition holds, and when those fail, people don't put that much effort into trying to describe the (more difficult) homotopy types. I'd be happy to hear that this is an unduly pessimistic view.

Answer 4

Various simplicial complexes arising in combinatorics have the Cohen Macaulay property. Such complexes are always (homologically) a wedge of spheres of the same dimension (the dimension of the complex) and also locally have this property. Shellability is an important combinatorial property that again implies the complex and all links to be wedge of spheres. There are interesting extensions of these concepts to the case of spheres of different dimension. Shifted complexes are simplicial complexes whose vertices have a total order and with the property that if S is a face and R is a face of the same dimension with smaller vertices (namely there is a bijection a:R->S so that v<=a(v) for every v) then R is a face. Shifted complexes are always wedge of spheres (of different dimensions) and there are interesting operations which associate to arbitrary simplicial complexes, such shifted complexes.

There are also quite a few interesting classes of simplicial complexes arising in combinatorics which are far from being wege of spheres. Take for example the chessbod complex whose faces are the locations on n nonattacking rooks in an n by n+1 chessboard board. for n=2 it is a hexagon for n=3 a torus for n=4 a certain pseudomanifold all links of vertices are tori, etc.

Answer 5

This is essentially a long comment in response to the other two answers.

One place in which interesting homotopy types do appear is in the study of Hom complexes of graphs.
Csorba and Lutz showed that Hom$(K_{2r} - C_{2r}, K_{r+1})$ is an orientable surface (not just up to homotopy, up to homeomorphism). Here $C_k$ denotes a length $k$ cycle. The genus is given by $r! \frac{r^2 - r -2}{2} + 1$, so it's never a sphere. They list some other interesting conjectures and particular computations.

More recently, Schultz proved a conjecture of Csorba stating that Hom$(C_5, K_{n+2})$ is homeomorphic to the Stiefel manifold $V_2 (\mathbb{R}^{n+1})$ of orthnormal 2-frames. This conjecture was made based on a complete calculation, by Kozlov, of the cohomology of Hom$(C_m, K_n); \mathbb{Z})$. Surprisingly, these complexes have 2-torsion in their cohomology when n is even (are there other complexes arising in combinatorics that have torsion in their cohomology?). Schutlz also showed that the colimit as $m\to \infty$ of the complexes Hom$(C_{2m}, K_n)$ is homotopy equivalent to the free loop space on $S^{n-2}$!

So, these are some instances in which people worked hard to get interesting answers.

I guess it's also worth pointing out that for any finite simplicial complex X and any graph T, there is a graph G (with looped vertices) such that Hom$(T, G) \simeq X$. This is a theorem of Anton Dochtermann . One might argue that this violates the spirit of the question, since one can't really say that these Hom complexes appear naturally; instead the graphs G in some rough sense look like the space X you're trying to model. (Specifically, G is the 1-skeleton of some subdivision of X, with loops placed on all the vertices.)