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
is the probability space on all graphs with vertex set
, with edges included with probability
, independently. Frequently
and
, and we say that
asymptotically almost surely (a.a.s) has property
if
as
.
A seminal result of Erdős and Rényi is that
is a sharp threshold for connectivity. In particular if
, then
is a.a.s. connected, and if
, then
is a.a.s. disconnected.
Nathan Linial and Roy Meshulam introduced a two-dimensional analogue of
, and proved an analogue of the Erdős-Rényi theorem. Their two-dimensional analogue is as follows: let
denote the probability space of all 2-dimensional (abstract) simplicial complexes with vertex set
and edge set
(i.e. a complete graph for the 1-skeleton), with each of the
triangles included independently with probability
.
Linial and Meshulam showed that
is a sharp threshold for vanishing of first homology
. (Here the coefficients are over
. This was generalized to
for all
by Meshulam and Wallach.) In other words, once
is much larger than
, every (one-dimensional) cycle is the boundary of some two-dimensional subcomplex.
Babson, Hoffman, and I showed that the threshold for vanishing of
is much larger: up to some log terms, the threshold is
. 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
be arbitrary but constant. If
then
, and if
then
, asymptotically almost surely.
It is relatively straightforward to show that when
is much larger than
, a.a.s.
. Almost all of the work in the paper is showing that when
is much smaller than
a.a.s.
. Our methods depend heavily on geometric group theory, and on the way to showing that
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
is a finite simplicial complex such that
for every subcomplex
, then
is homotopy equivalent to a wedge of circle, spheres, and projective planes.
(Here
denotes the number of
-dimensional faces.)
Corollary. With hypothesis as above, the fundamental group
is isomorphic to a free product
, for some number of
‘s and
‘s.
It is relatively easy to check that if
then with high probability subcomplexes of
on a bounded number of vertices satisfy the hypothesis of this theorem. (Of course
itself does not, since it has
and roughly
as
approaches
.)
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
is hyperbolic as well.
This gives a linear isoperimetric inequality on
which we can “lift” to a linear isoperimetric inequality on
.
But if
is simply connected and satisfies a linear isoperimetric inequality, then that would imply that every
-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
for vanishing of
. It is tempting to think that
, since this is the threshold for vanishing of
for every integer
. 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
as
, so in particular it does not rule out torsion in integer homology that grows with
.
As far as we know at the moment, no one has written down any improvements to the trivial bounds on
, that
. 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.