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.