The fundamental group of random 2-complexes

Eric Babson, Chris Hoffman, and I recently posted major revisions of our preprint, “The fundamental group of random 2-complexes” to the arXiv. This article will appear in Journal of the American Mathematical Society. This note is intended to be a high level summary of the main result, with a few words about the techniques.

The Erdős–Rényi random graph G(n,p) is the probability space on all graphs with vertex set [n] = \{ 1, 2, \dots, n \}, with edges included with probability p, independently. Frequently p = p(n) and n \to \infty, and we say that G(n,p) asymptotically almost surely (a.a.s) has property \mathcal{P} if \mbox{Pr} [ G(n,p) \in \mathcal{P} ] \to 1 as n \to \infty.

A seminal result of Erdős and Rényi is that p(n) = \log{n} / n is a sharp threshold for connectivity. In particular if p > (1+ \epsilon) \log{n} / n, then G(n,p) is a.a.s. connected, and if p < (1- \epsilon) \log{n} / n, then G(n,p) is a.a.s. disconnected.

Nathan Linial and Roy Meshulam introduced a two-dimensional analogue of G(n,p), and proved an analogue of the Erdős-Rényi theorem. Their two-dimensional analogue is as follows: let Y(n,p) denote the probability space of all 2-dimensional (abstract) simplicial complexes with vertex set [n] and edge set {[n] \choose 2} (i.e. a complete graph for the 1-skeleton), with each of the { n \choose 3} triangles included independently with probability p.

Linial and Meshulam showed that p(n) = 2 \log{n} / n is a sharp threshold for vanishing of first homology H_1(Y(n,p)). (Here the coefficients are over \mathbb{Z} / 2. This was generalized to \mathbb{Z} /p for all p by Meshulam and Wallach.) In other words, once p is much larger than 2 \log{n} / n, every (one-dimensional) cycle is the boundary of some two-dimensional subcomplex.

Babson, Hoffman, and I showed that the threshold for vanishing of \pi_1 (Y(n,p)) is much larger: up to some log terms, the threshold is p = n^{-1/2}. In other words, you must add a lot more random two-dimensional faces before every cycle is the boundary of not any just any subcomplex, but the boundary of the continuous image of a topological disk. A precise statement is as follows.

Main result Let \epsilon >0 be arbitrary but constant. If p \le n^{-1/2 - \epsilon} then \pi_1 (Y(n,p)) \neq 0, and if p \ge n^{-1/2 + \epsilon} then \pi_1 (Y(n,p)) = 0, asymptotically almost surely.

It is relatively straightforward to show that when p is much larger than n^{-1/2}, a.a.s. \pi_1 =0. Almost all of the work in the paper is showing that when p is much smaller than n^{-1/2} a.a.s. \pi_1 \neq 0. Our methods depend heavily on geometric group theory, and on the way to showing that \pi_1 is non-vanishing, we must show first that it is hyperbolic in the sense of Gromov.

Proving this involves some intermediate results which do not involve randomness at all, and which may be of independent interest in topological combinatorics. In particular, we must characterize the topology of sufficiently sparse two-dimensional simplicial complexes. The precise statement is as follows:

Theorem. If \Delta is a finite simplicial complex such that f_2 (\sigma) / f_0(\sigma) \le 1/2 for every subcomplex \sigma, then \Delta is homotopy equivalent to a wedge of circle, spheres, and projective planes.

(Here f_i denotes the number of i-dimensional faces.)

Corollary. With hypothesis as above, the fundamental group \pi_1( \Delta) is isomorphic to a free product \mathbb{Z} * \mathbb{Z} * \dots * \mathbb{Z} / 2 * \mathbb{Z}/2, for some number of \mathbb{Z}‘s and \mathbb{Z} /2‘s.

It is relatively easy to check that if p = O(n^{-1/2 - \epsilon}) then with high probability subcomplexes of Y(n,p) on a bounded number of vertices satisfy the hypothesis of this theorem. (Of course Y(n,p) itself does not, since it has f_0 = n and roughly f_2 \approx n^{5/2} as p approaches n^{-1/2}.)

But the corollary gives us that the fundamental group of small subcomplexes is hyperbolic, and then Gromov’s local-to-global principle allows us to patch these together to get that \pi_1 ( Y(n,p) ) is hyperbolic as well.
This gives a linear isoperimetric inequality on pi_1 which we can “lift” to a linear isoperimetric inequality on Y(n,p).

But if Y(n,p) is simply connected and satisfies a linear isoperimetric inequality, then that would imply that every 3-cycle is contractible using a bounded number of triangles, but this is easy to rule out with a first-moment argument.

There are a number of technical details that I am omitting here, but hopefully this at least gives the flavor of the argument.

An attractive open problem in this area is to identify the threshold t(n) for vanishing of H_1( Y(n,p), \mathbb{Z}). It is tempting to think that t(n) \approx 2 \log{n} / n, since this is the threshold for vanishing of H_1(Y(n,p), \mathbb{Z} / m) for every integer m. This argument would work for any fixed simplicial complex but the argument doesn’t apply in the limit; Meshulam and Wallach’s result holds for fixed m as n \to \infty, so in particular it does not rule out torsion in integer homology that grows with n.

As far as we know at the moment, no one has written down any improvements to the trivial bounds on t(n), that 2 \log{n} / n \le t(n) \le n^{-1/2}. Any progress on this problem will require new tools to handle torsion in random homology, and will no doubt be of interest in both geometric group theory and stochastic topology.


Coloring the integers

Here is a problem I composed, which recently appeared on the Colorado Mathematical Olympiad.

If one wishes to color the integers so that every two integers that differ by a factorial get different colors, what is the fewest number of colors necessary?

I might describe a solution, as well as some related history, in a future post. But for now I’ll just say that Adam Hesterberg solved this problem at Canada/USA Mathcamp a few summers ago, claiming the $20 prize I offered almost as soon as I offered it. At the time, I suspected but still did not know the exact answer.

Although the wording of the problem strongly suggests that the answer is finite, I don’t think that this is entirely obvious.

Along those lines, here is another infinite graph with finite chromatic number.

If one wishes to color the points of the Euclidean plane so that every two points at distance one get different colors, what is the fewest number of colors necessary?

This is one of my favorite unsolved math problems, just for being geometrically appealing and apparently intractably hard. After fifty years of many people thinking about it, all that is known is that the answer is 4, 5, 6, or 7. Recent work of Shelah and Soifer suggests that the exact answer may depend on the choice of set theoretic axioms.

This inspired the following related question.

If one wishes to color the points of the Euclidean plane so that every two points at factorial distance get different colors, do finitely many colors suffice?

More generally, if S is a sequence of positive real numbers that grows quickly enough (say exponentially), and one forbids pairs points at distance s from receiving the same color, one would suspect that finitely many colors suffice. On the other hand, if S grows slowly enough (say linearly), one might expect that infinitely many colors are required.

Francisco Santos disproves Hirsch conjecture

The Hirsch conjecture has been around for over 50 years. The conjecture states that a d-dimensional polytope with n facets has diameter at most n-d. (The facets of a polytope are the maximal dimensional faces (i.e. the (d-1)-dimensional faces), and saying that the diameter is at most n-d is just saying that every pair of vertices can be connected by a path of length at most n-d.)

The upper bounds on diameter are very far away from n-d; in fact no bound that is even polynomial (much less linear) in n and d is known. It was considered substantial progress when Gil Kalai got the first subexponential upper bounds. This fact led many to speculate that the conjecture is false, and apparently Victor Klee encouraged many people to try disproving it over the years.

Francisco Santos has just announced an explicit counterexample to the Hirsch conjecture, in dimension d = 43 with n =86 facets. Details to be described at the Grünbaum–Klee meeting in Seattle this summer.

To researchers on polytopes, this result may not be too surprising. Nevertheless, it is an old problem and it is nice to see it finally resolved. And there is something pleasing about finding explicit counterexamples in higher dimensional spaces. It offers a concrete way to see how bad our intuition for higher dimensions really is. Kahn and Kalai’s spectacular counterexample to “Borsuk’s conjecture” (in dimension d = 1325) comes to mind. I look forward to seeing the details of Santos’s construction.

A conjecture concerning random cubical complexes

Nati Linial and Roy Meshulam defined a certain kind of random two-dimensional simplicial complex, and found the threshold for vanishing of homology. Their theorem is in some sense a perfect homological analogue of the classical Erdős–Rényi characterization of the threshold for connectivity of the random graph.

Linial and Meshulam’s definition was as follows. Y(n,p) is a complete graph on n vertices, with each of the {n \choose 3} triangular faces inserted independently with probability p, which may depend on n. We say that Y(n,p) almost always surely (a.a.s) has property \mathcal{P} if the probability that Y(n,p) \in \mathcal{P} tends to one as n \to \infty.

Nati Linial and Roy Meshulam showed that if \omega is any function that tends to infinity with n and if p = (\log{n} + \omega) / n then a.a.s H_1( Y(n,p) , \mathbb{Z} / 2) =0 , and if p = (\log{n} - \omega) / n then a.a.s H_1( Y(n,p) , \mathbb{Z} / 2)  \neq 0 .

(This result was later extended to arbitrary finite field coefficients and arbitrary dimension by Meshulam and Wallach. It may also be worth noting for the topologically inclined reader that their argument is actually a cohomological one, but in this setting universal coefficients gives us that homology and cohomology are isomorphic vector spaces.)

Eric Babson, Chris Hoffman, and I found the threshold for vanishing of the fundamental group \pi_1(Y(n,p)) to be quite different. In particular, we showed that if \epsilon > 0 is any constant and p \le n^{-1/2 -\epsilon} then a.a.s. \pi_1 ( Y(n,p) ) \neq 0 and if p \ge n^{ -1/2 + \epsilon} then a.a.s. \pi_1 ( Y(n,p) )  = 0 . The harder direction is to show that on the left side of the threshold that the fundamental group is nontrivial, and this uses Gromov’s ideas of negative curvature. In particular to show that the \pi_1 is nontrivial we have to show first that it is a hyperbolic group.

[I want to advertise one of my favorite open problems in this area: as far as I know, nothing is known about the threshold for H_1( Y(n,p) , \mathbb{Z}) , other than what is implied by the above results.]

I was thinking recently about a cubical analogue of the Linial-Meshulam set up. Define Z(n,p) to be the one-skeleton of the n-dimensional cube with each square two-dimensional face inserted independently with probability p. This should be the cubical analogue of the Linial-Mesulam model? So what are the thresholds for the vanishing of H_1 ( Z(n,p) , \mathbb{Z} / 2) and \pi_1 ( Z(n,p) ) ?

I just did some “back of the envelope” calculations which surprised me. It looks like p must be much larger (in particular bounded away from zero) before either homology or homotopy is killed. Here is what I think probably happens. For the sake of simplicity assume here that p is constant, although in realty there are o(1) terms that I am suppressing.

(1) If p  < \log{2} then a.a.s H_1 ( Z(n,p) , \mathbb{Z} /2 ) \neq 0, and if p  > \log{2} then a.a.s H_1 ( Z(n,p) , \mathbb{Z} /2 ) = 0.

(2) If p  < (\log{2})^{1/4} then a.a.s. \pi_1 ( Z(n,p) ) \neq 0, and if p > (\log{2})^{1/4} then a.a.s. \pi_1 ( Z(n,p) ) = 0.

Perhaps in a future post I can explain where the numbers \log{2} \approx 0.69315 and (\log{2})^{1/4} \approx 0.91244 come from. Or in the meantime, I would be grateful for any corroborating computations or counterexamples.

Topological Turán theory

I just came across the following interesting question of Nati Linial.

If a two-dimensional simplicial complex has n vertices and \Omega(n^{5/2}) faces, does it necessarily contain an embedded torus?

I want to advertise this question to a wider audience, so I’ll explain first why I think it is interesting.

First of all this question makes sense in the context of Turán theory, a branch of extremal combinatorics. The classical Turán theorem gives that if a graph on n vertices has more than \displaystyle{ \left( 1-\frac{1}{r} \right) \frac{n^2}{2} } edges then it necessarily contains a complete subgraph K_r on r vertices. This is tight for every r and n.

One could ask instead how many edges one must have before there is forced to be a cycle subgraph, where it doesn’t matter what the length of the cycle is. This is actually an easier question, and it is easy to see out that if one has n edges there must be a cycle.
It also seems more natural, in that it can be phrased topologically: how many edges must be added to n vertices before we are forced to contain an embedded image of the circle?

What is the right two-dimensional analogue of this statement? In particular, is there a constant C such that a two-dimensional simplicial complex with n vertices and at least C n^2 two-dimensional faces must contain an embedded sphere S^2? If so, then this is essentially best possible. By taking a cone over a complete graph on n-1 vertices, one constructs a two-complex on n vertices with {n -1 \choose 2} faces and no embedded spheres. Without having thought about it at all, I am not sure how to do better.

In any case, the corresponding question for torus seems more interesting, but for different reasons. In a paper with Eric Babson and Chris Hoffman we looked at the fundamental group of random two-complexes, as defined by Linial and Meshulam, and found the rough threshold for vanishing of the fundamental group. To show that the fundamental group was nontrivial when the number of faces was small required a lot of work — in particular, in order to apply Gromov’s local-to-global method for hyperbolicity, we needed to prove that the space was locally negatively curved, and this meant classifying the homotopy type of subcomplexes up to a large but constant size.

It turned out that the small subcomplexes were all homotopy equivalent to wedges of circles, spheres, and projective planes. In particular, we show that there are not any torus subcomplexes, at least not of bounded size. (Linial may have recently shown that there are not embedded tori, even of size tending to infinity with n.) On the other hand, just on the other side of the threshold embedded tori abound in great quantity. It is interesting that something similar happens in the density random groups of Gromov — that the threshold for vanishing of the density random group corresponds to the presence of tori subcomplex in the naturally associated two-complex. It is not clear to me if this is a general phenomenon, coming geometrically from the fact that a torus admits a flat metric.

Some of the great successes of the probabilistic method in combinatorics have been in existence proofs when constructions are hard or impossible to come by. It would be nice to have interesting or extremal topological examples produced this way. Nati’s question suggests an interesting family of extremal problems in topological combinatorics, and it might make sense that in certain cases, random simplicial complexes have nearly maximally many faces for avoiding a particular embedded subspace.

Update: Nati pointed me to the paper Sós, V. T.; Erdos, P.; Brown, W. G., On the existence of triangulated spheres in $3$-graphs, and related problems. Period. Math. Hungar. 3 (1973), no. 3-4, 221–228.
Here it is shown that n^{5/2} is the right answer for the sphere. Their lower bound is constructive, based on projective planes over finite fields. Nati said that being initially unaware of this paper, he found a probabilistic proof that works just as well as a lower bound for every fixed 2-manifold. So it seems that the main problem here is to find a matching upper bound for the torus.

The Rado complex

A simplicial complex is said to be flag if it is the clique complex of its underlying graph. In other words, one starts with the graph and add all simplices of all dimensions that are compatible with this 1-skeleton. A subcomplex F' of a flag complex F is said to be induced if it is flag, and if whenever vertices x, y \in  F' and \{ x,y \} is an edge of F, we also have that \{ x,y \} is an edge of F'.

Does there exist a flag simplicial complex \Delta with countably many vertices, such that the following extension property holds?

[Extension property] For every finite or countably infinite flag simplicial complex X and vertex v \in X, and for every embedding of X-v as an induced subcomplex i: X -v \hookrightarrow \Delta , i can be extended to an embedding \widetilde{i}: X \hookrightarrow \Delta of X as an induced subcomplex.

It turns out that such a \Delta does exist, and it is unique up to isomorphism (both combinatorially and topologically). Other interesting properties of \Delta immediately follow.

\Delta contains homoemorphic copies of every finite and countably infinite simplicial complex as induced subcomplexes.

– The link of every face \sigma \in \Delta is homeomorphic to \Delta itself.

– The automorphism group of \Delta acts transitively on d-dimensional faces for every d.

– Deleting any finite number of vertices or edges of \Delta and the accompanying faces does not change its homeomorphism type.

Here is an easy way to describe \Delta. Take countably many vertices, say labeled by the positive integers. Choose a probability p such that 0 < p < 1, and for each pair of integers \{ m,n \}, connect m to n by an edge with probability p. Do this independently for every edge.

This is sometimes called the Rado graph, and because it is unique up to isomorphism (and in particular because it does not depend on p) it is sometimes also called the random graph. It is also possible to construct the Rado graph purely combinatorially, without resorting to probability. The \Delta I have in mind is of course just the clique complex of the Rado graph.

We can filter the complex \Delta by setting \Delta(n) to be the induced subcomplex on all vertices with labels \le n, and this allows us to ask more refined questions. (Now the choice of p affects the asymptotics, so we assume p = 1/2.) From the perspective of homotopy theory, \Delta is not a particularly interesting complex; it is contractible. (This is an exercise, one should check this if it is not obvious!) However, \Delta(n) has interesting topology.

As n \to \infty, the probability that \Delta(n) is contractible is going to 0. It was recently shown that \Delta(n) has asymptotically almost surely (a.a.s.) at least \Omega( \log{ \log{ n}} ) nontrivial homology groups, concentrated around dimension \log_2{n}. For comparison, the dimension of \Delta(n) is d \approx 2 \log_2{n}.

I think one can probably show using the techniques from this paper that there is a.a.s. no nontrivial homology above dimension d/2 or below dimension d/4. It is still not clear (at least to me) what happens between dimensions d/4 and d/2. It seems that a naive Morse theory argument can give that the expected dimension of homology is small in this range, but to show that it is zero would take a more refined Morse function. Perhaps a good topic for another post would be “Morse theory in probability.”

Another question: given a non-contractible induced subcomplex (say an embedded d-dimensional sphere) \Delta' \subset \Delta on a set S of k vertices, how many vertices f(k) should one expect to add to S before \Delta' becomes contractible in the larger induced subcomplex? For example, it seems that once you have added about 2^k vertices, it is reasonably likely that one of these vertices induces a cone over \Delta', but is it possible that the subcomplex becomes contractible with far fewer vertices added?

The foolproof cube – a study in symmetry

Besides being a fun toy, and perhaps the most popular puzzle in human history, the Rubik’s Cube is an interesting mathematical example. It provides a nice example of a nonabelian group, and in another article I may discuss some features of this group structure. This expository article is about an experiment, where I made Rubik’s cubes with two or three colors, instead of six. In particular, I want to mention an interesting observation made by Dave Rosoff about one of the specially colored cubes: It turns out to be foolproof, in the sense that no matter how one breaks it apart and reassembles the pieces, it is still solvable by twisting the sides. It is well known that this is not a property that stock Rubik’s Cubes have.

The first observation about the physical construction of the cube is that it is made out of 21 smaller plastic pieces: a middle piece with 6 independently spinning center tiles, 12 corner cubies, and 8 edge cubies.  The frame includes 6 of the stickers. Each corner cubie has 3, and each edge cubie has 2. (And this accounts for all of the 6 \times 9 =54 = 6+ 12 \times 3 + 8 \times 2 stickers. These stickers are on a solid piece of plastic, so they always stay next to each other, no matter matter how much you scramble it by twisting the sides. (I remember getting really mad as a kid, after figuring out that someone else had messed around with the stickers on my cube. Still a pet peeve, taking stickers off a cube is like fingernails on a chalkboard for me.)

So anyway, it’s impossible to get two yellow stickers on the same edge cubie, for example, because that would make the cube impossible to solve: you couldn’t ever get the two stickers onto the same side. But this is not the only thing that can’t happen. Let’s restrict ourselves from now on to just the positions you can get to by taking the cube apart into plastic pieces, and putting them back together. If you take it apart, and put it back together randomly, will you necessarily be able to solve it by only twisting sides? (Of course you can always solve it by taking it back apart and putting it back together solved!) I knew, empirically, as a kid that you might not be able to solve it if you put it together haphazardly. Someone told me in high school that if you put it together “randomly,” your chances that it was solvable were exactly 1 in 12, and explained roughly why: it is impossible to flip an edge (gives a factor of 2), rotate a corner (a factor of 3), or to switch any two cubies (another factor of 2).

This seemed plausible at the time, but it wasn’t until a graduate course in algebra that I could finally make mathematical sense of this. In fact, one of the problems on the take-home final was to prove that it’s impossible to flip any edge (leaving the rest of the cube untouched!), through any series of twists. I thought about it for a day or two, and was extremely satisfied to finally figure it out, how to prove something that I had known in my heart to be true since I was a kid. It is a fun puzzle, and one can write out a proof that doesn’t really use group theory in any essential way (although to be fair, group theory does provide a convenient language, and concise ways of thinking about things). For example, it is possible to describe a number 0 or 1 to every position, such that the number doesn’t change when you twist any side (i.e. it is invariant). Then provided that the property prescribes a 0 to a solved cube and a 1 to a cube with a flipped edge, the invariance gives  that the flipped edge cube is unsolvable.

Several years ago, I got inspired to try different colorings of a Rubik’s Cube, just allowing some of the sides to have the same color. I was picky about how I wanted to do it, however. Each color class should “look the same,” up to a relabeling. A more precise way to say this is that every permutation of the colors is indistinguishable from some isometry. (Isometries of the cube are its symmetries: reflections, and rotations, and compositions of these. There are 48 in total.)

It turns out that this only gives a few possibilities. The first is the usual coloring by 6-colors. Although there are several ways to put 6 colors on the faces of a cube,  for our purposes here there is really only one 6-color cube. There is also the “Zen cube,” with only one color. (“Always changing, but always the same.”) But there are a few intermediate possibilities that are interesting. First, with two colors, once can two-color the faces of a cube in essentially two different ways. Note that since we want each color class to look the same, each color gets three sides. The three sides of a color class either all three meet at a corner, or they don’t. And these are the only two possibilities, after taking into account all of the symmetries.

So I bought some blank cubes and stickers, and made all four of the mathematically interesting possibilities. (I keep meaning to make a nice Zen cube, perhaps more interesting philosophically than mathematically, but I still haven’t gotten around to it. ) My friend Dave Rosoff and I played around with all of these, and found them somewhat entertaining. A first surprise was that they seem harder to solve than a regular Rubik’s cube. Seems like it should be easier, in terms of various metrics: the number of indistinguishable positions being much smaller, or equiavalently, the number of mechanical positions which are indistinguishable from the “true” solved position being much bigger. However in practice, what happens for many experience cube solvers, is that they get into positions that they don’t recognize at the end: the same-colored stickers seem to mask your true position. Nevertheless, an experienced solver can handle all four of these cubes without too much difficulty.

When playing around with them, occasionally a cubie would pop out fall to the floor. The thing to do is to just pop the piece back in arbitrarily, and the solve it as far as you can. It is usually an edge that pops, so the probability of having a solvable cube is 1/2.  And if not, one can tell at the end, and then remedies the situation by flipping any edge back. Dave noticed something special about one of these four cubes, I think just from enough experience with solving it: no matter which piece got popped out, when he popped it back in randomly, the cube still seemed to be solvable. He thought it seemed too frequent to be a coincidence, so after a while of chatting about it, we convinced ourselves that this cube indeed had a special property: if one takes it apart into its 21 pieces, and reassembles it arbitrarily, it is always solvable by twists, a property we described as, “foolproof.” We talked it about it for a while longer, and convinced ourselves that this is the only foolproof cube, up to symmetry and permuting colors. (Well, the Zen cube is foolproof too.)

So which of these four cubes is foolproof? This puzzle yields to a few basic insights, and does not actually require making models of each type of cube, although I would encourage anyone to do so who has extra blank cubes and stickers around, or who wants a neat Cube variant for their collection.