Why do wedges of spheres often appear in combinatorics? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T22:40:31Z http://mathoverflow.net/feeds/question/17370 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/17370/why-do-wedges-of-spheres-often-appear-in-combinatorics Why do wedges of spheres often appear in combinatorics? Michał Kukieła 2010-03-07T10:10:41Z 2010-09-23T00:06:01Z <p>Robin Forman writes in <a href="http://www.emis.de/journals/SLC/wpapers/s48forman.pdf" rel="nofollow">"A User's Guide to Discrete Morse Theory"</a>:</p> <blockquote> <p>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.</p> </blockquote> <p>The question is: "Why so many simplicial complexes that arise in combinatorics are homotopy equivalent to a wedge of spheres?"</p> http://mathoverflow.net/questions/17370/why-do-wedges-of-spheres-often-appear-in-combinatorics/17378#17378 Answer by Allen Knutson for Why do wedges of spheres often appear in combinatorics? Allen Knutson 2010-03-07T13:33:26Z 2010-03-07T13:33:26Z <p>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.</p> http://mathoverflow.net/questions/17370/why-do-wedges-of-spheres-often-appear-in-combinatorics/17387#17387 Answer by Allen Hatcher for Why do wedges of spheres often appear in combinatorics? Allen Hatcher 2010-03-07T16:12:50Z 2010-03-07T16:12:50Z <p>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.</p> http://mathoverflow.net/questions/17370/why-do-wedges-of-spheres-often-appear-in-combinatorics/20035#20035 Answer by Dan Ramras for Why do wedges of spheres often appear in combinatorics? Dan Ramras 2010-04-01T04:39:05Z 2010-04-01T18:47:06Z <p>This is essentially a long comment in response to the other two answers. </p> <p>One place in which interesting homotopy types do appear is in the study of Hom complexes of graphs.<br> <a href="http://arxiv.org/abs/math/0510177" rel="nofollow"> Csorba and Lutz </a> showed that Hom<code>$(K_{2r} - C_{2r}, K_{r+1})$</code> is an orientable surface (not just up to homotopy, up to homeomorphism). Here <code>$C_k$</code> denotes a length <code>$k$</code> cycle. The genus is given by <code>$r! \frac{r^2 - r -2}{2} + 1$</code>, so it's never a sphere. They list some other interesting conjectures and particular computations.</p> <p>More recently, <a href="http://arxiv.org/abs/math/0510535" rel="nofollow"> Schultz </a> proved a conjecture of Csorba stating that Hom<code>$(C_5, K_{n+2})$</code> is homeomorphic to the Stiefel manifold <code>$V_2 (\mathbb{R}^{n+1})$</code> or orthnormal 2-frames. This conjecture was made based on a complete calculation, by Kozlov, of the cohomology of Hom<code>$(C_m, K_n); \mathbb{Z})$</code>. 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 <code>$m\to \infty$</code> of the complexes <code>Hom$(C_{2m}, K_n)$</code> is homotopy equivalent to the free loop space on $S^{n-2}$!</p> <p>So, these are some instances in which people worked hard to get interesting answers.</p> <p>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<code>$(T, G) \simeq X$</code>. This is a theorem of <a href="http://arxiv.org/abs/math/0702471" rel="nofollow"> Anton Dochtermann </a>. 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.)</p> http://mathoverflow.net/questions/17370/why-do-wedges-of-spheres-often-appear-in-combinatorics/39653#39653 Answer by Matthew Kahle for Why do wedges of spheres often appear in combinatorics? Matthew Kahle 2010-09-22T20:29:24Z 2010-09-23T00:06:01Z <p>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$.</p> <p>The main point of my paper <a href="http://arxiv.org/abs/math/0605536" rel="nofollow">Topology of random clique complexes</a> 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&lt; d/4$, and that almost all of whatever homology remains is concentrated in the middle dimension $k=\lfloor d/2 \rfloor$.</p> <p>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.</p> <p>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.)</p> http://mathoverflow.net/questions/17370/why-do-wedges-of-spheres-often-appear-in-combinatorics/39665#39665 Answer by Gil Kalai for Why do wedges of spheres often appear in combinatorics? Gil Kalai 2010-09-22T22:51:35Z 2010-09-22T22:57:35Z <p>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&lt;=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. </p> <p>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.</p>