# Geometry and topology of random 2-complexes

A.E. Costa and M. Farber

(June 23, 2014)

Abstract: We study random 2-dimensional complexes in the Linial - Meshulam
model and prove that the fundamental group of a random 2-complex $Y$ has
cohomological dimension $\leq 2$ if the probability parameter satisfies $p\ll
n^{-3/5}$. Besides, for $n^{-3/5}\ll p\ll n^{-1/2-\epsilon}$ the fundamental
group $\pi_{1}(Y)$ has elements of order two and is of infinite cohomological
dimension. We also prove that for $p\ll n^{-1/2-\epsilon}$ the fundamental
group of a random 2-complex has no $m$-torsion, for any given odd prime $m\geq
3$. We find a simple algorithmically testable criterion for a subcomplex of a
random 2-complex to be aspherical; this implies that (for $p\ll
n^{-1/2-\epsilon}$) any aspherical subcomplex of a random 2-complex satisfies
the Whitehead conjecture. We use inequalities for Cheeger constants and
systoles of simplicial surfaces to analyse spheres and projective planes lying
in random 2-complexes. Our proofs exploit the uniform hyperbolicity property
of random 2-complexes (Theorem 3.4).

##  1 Introduction and statements of the main results

A model producing random simplicial complexes was recently suggested and
studied by Linial and Meshulam [13] and further by Meshulam and Wallach [14];
it is a high-dimensional generalisation of one of the Erdös and Rényi models
of random graphs [7]. In the Linial - Meshulam model one generates a random
$d$-dimensional complex $Y$ by considering the full $d$-dimensional skeleton
of the simplex $\Delta_{n}$ on vertices $\\{1,\dots,n\\}$ and retaining
$d$-dimensional faces independently with probability $p$. The work of
Linial–Meshulam and Meshulam–Wallach provides threshold functions for the
vanishing of the $(d-1)$-st homology groups of random complexes with
coefficients in a finite abelian group. Threshold functions for the vanishing
of the $d$-th homology groups were subsequently studied by Kozlov [12].

Significant progress in understanding the topology of random 2-complexes was
made by Babson, Hoffman, and Kahle [2] who investigated the fundamental groups
of random 2-complexes. They showed that the fundamental group of a random
2-complex is either nontrivial and Gromov hyperbolic (for $p\ll
n^{-1/2-\epsilon}$) or trivial (if $p^{2}n-3\log n\to\infty$), a.a.s.111The
symbol a.a.s. is an abbreviation of “asymptotically almost surely”, which
means that the probability that the corresponding statement is valid tends to
$1$ as $n\to\infty$.

In the paper [5] it was proven that a random 2-complex $Y$ collapses to a
graph if $p\ll n^{-1}$ and therefore its fundamental group is free.

The preprint [1] suggests an explicit constant $\gamma$ such that for any
$c<\gamma$ a random $Y\in Y(n,c/n)$ is either collapsible to a graph or
contains a tetrahedron.

It is important to have a model producing random aspherical 2-dimensional
complexes $Y$. A connected simplicial complex $Y$ is said to be aspherical if
$\pi_{i}(Y)=0$ for all $i\geq 2$; this is equivalent to the requirement that
the universal cover of $Y$ is contractible. For 2-dimensional complexes $Y$
the asphericity is equivalent to the vanishing of the second homotopy group
$\pi_{2}(Y)=0$, or equivalently, that any continuous map $S^{2}\to Y$ is
homotopic to a constant map. Random aspherical 2-complexes could be helpful
for testing probabilistically the open problems of two-dimensional topology,
such as the Whitehead conjecture. This conjecture stated by J.H.C. Whitehead
in 1941 claims that a subcomplex of an aspherical 2-complex is also
aspherical. Surveys of results related to the Whitehead conjecture can be
found in [3], [17].

The Linial-Meshulam model of random 2-complexes produces an aspherical complex
$Y$ if $p\ll n^{-1}$, when $Y$ is homotopy equivalent to a graph, a.a.s.;
however for $p\gg n^{-1}$ a random 2-complex is not aspherical since it
contains a tetrahedron as a subcomplex, a.a.s. In [6] the authors studied
asphericable 2-complexes, which can be made aspherical by deleting a few faces
belonging to tetrahedra. The result of [6] states that random 2-complexes in
the Linial - Meshulam model are asphericable in the range $p\ll n^{-46/47}$.

In this paper we revisit the hyperbolicity theorem of Babson, Hoffman and
Kahle [2] having in mind two principal goals: firstly, we simplify and make
more transparent the main ideas of the proof; secondly we observe that the
arguments of [2] give in fact a slightly stronger statement: a uniform lower
bound on the isoperimetric constants of all subcomplexes of random complexes
(see Theorem 3.4 below and its full proof in §6).

The key role in this paper plays Theorem 2.5 which gives a topological
classification of minimal cycles $Z$ with the property $\mu(Z)>1/2$.

Now we state the major results obtained in this paper.

Theorem A. [See Corollary 5.9 and Proposition 5.11] If $p\ll n^{-3/5}$ then
the fundamental group $\pi_{1}(Y)$ of a random 2-complex $Y\in Y(n,p)$ has
cohomological dimension at most 2, a.a.s. In particular, $\pi_{1}(Y)$ is
torsion free, a.a.s. Moreover, if $\frac{c}{n}<p\ll n^{-3/5}$, where $c>3$,
then ${\rm{cd}}(\pi_{1}(Y))=2$, a.a.s.  The following theorem states that
2-torsion appears in the fundamental group $\pi_{1}(Y)$ once the probability
parameter $p$ crosses the threshold $n^{-3/5}$. Theorem B. [See Theorem 4.5]
If for some $0<\epsilon<0.1$ the probability parameter $p$ satisfies

$n^{-3/5}\ll p\ll n^{-1/2-\epsilon}$

then the fundamental group $\pi_{1}(Y)$ of a random 2-complex $Y\in Y(n,p)$
has nontrivial elements of order two and consequently
${\rm{cd}}(\pi_{1}(Y))=\infty$, a.a.s.

The next result complements Theorem B.

Theorem C. [See Theorem 4.6] Let $m\geq 3$ be an odd prime. If for some
$\epsilon>0$ the probability parameter $p$ satisfies $p\ll n^{-1/2-\epsilon}$
then, with probability tending to one as $n\to\infty$, a random 2-complex
$Y\in Y(n,p)$ has the following property: the fundamental group
$\pi_{1}(Y^{\prime})$ of any subcomplex $Y^{\prime}\subset Y$ has no
$m$-torsion.

The next statement describes aspherical subcomplexes of random 2-complexes. It
is a strengthening of the main result of [6]. Theorem D. [See Theorem 5.5]
Assume that $p\ll n^{-1/2-\epsilon}$ for a fixed $\epsilon>0$. Then a random
2-complex $Y\in Y(n,p)$ has the following property with probability tending to
one as $n\to\infty$: any subcomplex $Y^{\prime}\subset Y$ is aspherical if and
only if it contains no subcomplexes $S\subset Y^{\prime}$ with at most
$2\epsilon^{-1}$ faces which are homeomorphic either to the sphere $S^{2}$,
the projective plane ${\mathbf{RP}}^{2}$ or the complexes $Z_{2},Z_{3}$ shown
on Figure 3.

Theorem D implies the following result which can be viewed as probabilistic
confirmation of the Whitehead Conjecture.

Corollary E. [The Whitehead Conjecture] Assume that $p\ll n^{-1/2-\epsilon}$
for a fixed $\epsilon>0$. Then a random 2-complex $Y\in Y(n,p)$ has the
following property with probability tending to one as $n\to\infty$: any
aspherical subcomplex $Y^{\prime}\subset Y$ satisfies the Whitehead
Conjecture, i.e. any subcomplex $Y^{\prime\prime}\subset Y^{\prime}$ is also
aspherical.

Proposition 5.11 describes the second Betti number of random aspherical
2-complexes obtained from a random 2-complex $Y\in Y(n,p)$ by deleting a
sequence of faces. It follows that these complexes have non-free fundamental
groups.

The following corollary states that a random 2-complex in the range $p\ll
n^{-1/2-\epsilon}$ contains no tori and no large spheres and projective
planes. Corollary F. [see Corollaries 3.5, 3.6, 3.7] Suppose that $p\ll
n^{-1/2-\epsilon}$, where $\epsilon>0$ is fixed. Then:

  1. (a)

A random 2-complex $Y\in Y(n,p)$ contains no subcomplex homeomorphic to the
torus $T^{2}$, a.a.s.

  2. (b)

A random 2-complex $Y\in Y(n,p)$ contains no subcomplex with more than
$2\epsilon^{-1}$ faces which is homeomorphic to the sphere $S^{2}$, a.a.s.

  3. (c)

A random 2-complex $Y\in Y(n,p)$ contains no subcomplex with more than
$\epsilon^{-1}$ faces which is homeomorphic to the real projective plane
${\mathbf{RP}}^{2}$, a.a.s.

Note that under the assumptions of Corollary F (as follows from the results of
[5]) any triangulated sphere with $\leq 2\epsilon^{-1}$ faces is contained in
a random 2-complex as a subcomplex and, besides, any triangulated real
projective plane with $\leq\epsilon^{-1}$ faces is contained in a random
2-complex, a.a.s. Thus Corollary F lists all spheres and projective planes
which cannot be found as subcomplexes of random complexes with probability
tending to one.

We know that for $p=n^{\alpha}$ with $\alpha>-1/2$ a random 2-complex $Y\in
Y(n,p)$ is simply connected and hence it has homotopy type of a wedge of
2-spheres, see [2]. Thus, a significant change in geometry and topology of
random 2-complexes happens around $p=n^{-1/2}$, and an outstanding challenge
for the research field is to analyse this event in more detail.

Figure 1 illustrates the behaviour of the cohomological dimension of the
fundamental group $\pi_{1}(Y)$ of a random 2-complex $Y\in Y(n,p)$. For
simplicity we assume here that $p=n^{\alpha}$ where $\alpha$ is a real
parameter, $\alpha\in(-\infty,0)$.

Figure 1: The cohomological dimension ${\rm cd}={\rm cd}(\pi_{1}(Y))$ of the
fundamental group of a random 2-complex $Y\in Y(n,p)$ where $p=n^{\alpha}$.

The behaviour of the torsion in the fundamental group $\pi_{1}(Y)$ of a random
2-complex $Y\in Y(n,p)$ is illustrated by Figure 2. Again, we assume here that
$p=n^{\alpha}$, where $\alpha\in(-\infty,0)$. We also know that $\pi_{1}(Y)$
has no $m$-torsion, where $m$ is an odd prime, for $p=n^{\alpha}$ with
$\alpha\not=-1/2$.

Figure 2: Torsion in the fundamental group of a random 2-complex $Y\in Y(n,p)$
where $p=n^{\alpha}$.

A few words about terminology we use in this paper. By a 2-complex we
understand a finite simplicial complex $Z$ of dimension $\leq 2$. The
$i$-dimensional simplexes of a 2-complex are called vertices (for $i=0$),
edges (for $i=1$) and faces (for $i=2$). A 2-complex is said to be pure if any
vertex and any edge are incident to a face. For an edge $e\subset Z$ we denote
by $\deg e=\deg_{Z}(e)$ the degree of $e$, i.e. the number of faces of $Z$
containing $e$. The union of edges of degree one is denoted $\partial Z$ and
is called the boundary of $Z$. We say that a 2-complex $Z$ is closed if
$\partial Z=\emptyset$.

We use the notations $P^{2}$ and ${\mathbf{RP}}^{2}$ for the real projective
plane.

For a 2-complex $X$ we denote by $\mu(X)$ the ratio $v/f$ where $v=v(X)$ is
the number of vertices and $f=f(X)$ is the number of faces in $X$. The symbol
$\tilde{\mu}(X)$ denotes

$\tilde{\mu}(X)=\min\mu(S)$

where $S\subset X$ runs over all subcomplexes. More information about the
properties of the invariants $\mu(X)$ and $\tilde{\mu}(X)$ and their relevance
to the containment problem for random complexes can be found in [2], [5]. For
convenience of the reader we shall state here one of the results which will be
used frequently in the paper, compare Theorem 15 in [5].

######  Lemma 1.1.

Let $\mathcal{F}$ be a finite collection of finite simplicial complexes.
Denote $\alpha=\min\\{\tilde{\mu}(X),X\in\mathcal{F}\\}$, and
$\beta=\max\\{\tilde{\mu}(X),X\in\mathcal{F}\\}$. Let
$A_{n}^{\mathcal{F}}\subset Y(n,p)$ denote the set of complexes $Y\in Y(n,p)$
which contain each of the complexes $X\in\mathcal{F}$ as a simplicial
subcomplex. Let $B_{n}^{\mathcal{F}}\subset Y(n,p)$ denote the set of
complexes $Y\in Y(n,p)$ which contain at least one of the complexes
$X\in\mathcal{F}$ as a simplicial subcomplex. Clearly
$A_{n}^{\mathcal{F}}\subset B_{n}^{\mathcal{F}}$. Then one has:

(1) If $p\ll n^{-\beta}$ then $\mathbb{P}(B_{n}^{\mathcal{F}})\to 0$ as
$n\to\infty$;

(2) If $p\gg n^{-\alpha}$ then $\mathbb{P}(A_{n}^{\mathcal{F}})\to 1$ as
$n\to\infty$.

In other words, (1) states that for small $p$ none of the complexes
$X\in\mathcal{F}$ is embeddable into a random 2-complex, a.a.s.; statement (2)
states that for large $p$ any complex $X\in\mathcal{F}$ is embeddable into a
random 2-complex, a.a.s.

##  2 Topology of minimal cycles

In this section we classify topologically the minimal cycles satisfying the
condition $\mu(Z)>1/2$; this result will be important for our study of
aspherical subcomplexes and the Whitehead conjecture in §5.

If $v\in Z$ is a vertex of a 2-complex $Z$ then the link of $v$ is a graph; we
denote by ${\rm{Sing}}(v)={\rm{Sing}}_{Z}(v)$ the number of connected
components of the link of $v$ minus one.

Let $Z$ be a finite pure 2-complex with the set of vertices $V(Z)$. The
closure of a connected component of the complement $Z-V(Z)$ is called a
strongly connected component of $Z$. A finite pure complex $Z$ is called
strongly connected if there is a unique strongly connected component. Note
that if $Z$ is path-connected and ${\rm{Sing}}(v)=0$ for any vertex $v\in
V(Z)$ then $Z$ is strongly connected.

Given a pure 2-complex $Z$, there is a canonically defined 2-complex
$\tilde{Z}$ with a natural surjective map $\tilde{Z}\to Z$, which is 1-1 on
$\tilde{Z}-V(\tilde{Z})$, such that ${\rm{Sing}}_{\tilde{Z}}(w)=0$ for any
vertex $w$ of $\tilde{Z}$. The complex $\tilde{Z}$ is obtained by multiplying
every vertex of $Z$ as many times as there are connected components in the
link of this vertex (in other words, we cut open any vertex $v$ with
${\rm{Sing}}(v)>0$ along the cut point). Clearly, $\tilde{Z}$ is strongly
connected if $Z$ is strongly connected. In this case one observes that $Z$ is
homotopy equivalent to the wedge sum $\tilde{Z}\vee S^{1}\vee
S^{1}\vee\dots\vee S^{1},$ where the number of $S^{1}$ summands equals
$\sum_{v\in V(Z)}{\rm{Sing}}(v).$ This gives the following corollary:

######  Corollary 2.1.

For any pure strongly connected 2-complex $Z$ one has

$b_{1}(Z)=b_{1}(\tilde{Z})+\sum_{v\in V(Z)}{\rm{Sing}}(v)\geq\sum_{v\in
V(Z)}{\rm{Sing}}(v).$

In particular, if $Z$ has at least one vertex with ${\rm{Sing}}(v)\geq 1$ then
$b_{1}(Z)\geq 1$.

######  Definition 2.2.

A finite pure 2-complex $Z$ is said to be a minimal cycle if $b_{2}(Z)=1$ and
for any proper subcomplex $Z^{\prime}\subset Z$ one has $b_{2}(Z^{\prime})=0$.

Clearly a minimal cycle must be closed (i.e. $\partial Z=\emptyset$) and
strongly connected. Indeed, if $Z_{1},\dots,Z_{k}$ are strongly connected
components of $Z$, $k\geq 2$, then $b_{2}(Z)=\sum b_{2}(Z_{i})$ and hence
exactly one component $Z_{i}$ has the second Betti number 1. Removing a face
from another component $Z_{j}$, $j\not=i$, will not affect the second Betti
number, which gives a contradiction.

The following easy statement will be useful later.

######  Lemma 2.3.

Let $\phi:Z_{1}\to Z_{2}$ be a simplicial map between finite 2-complexes such
that $b_{2}(Z_{1})\geq 1$ and $Z_{2}$ is a minimal cycle. Suppose that $\phi$
maps bijectively the set of faces of $Z_{1}$ onto the set of faces of $Z_{2}$
(and in particular, faces of $Z_{1}$ do not degenerate under $\phi$). Then
$Z_{1}$ is also a minimal cycle; in particular $Z_{1}$ is strongly connected.

###### Proof.

Assuming that $Z_{1}$ is not a minimal cycle we may find a proper subcomplex
$Z_{1}^{\prime}\subset Z_{1}$ with $b_{2}(Z^{\prime}_{1})=1$. Then our
assumptions imply that the subcomplex $\phi(Z_{1}^{\prime})\subset Z_{2}$ is
proper and carries a nontrivial 2-cycle, i.e. $b_{2}(\phi(Z_{1}^{\prime}))\geq
1$ contradicting the minimality of $Z_{2}$. ∎

######  Lemma 2.4.

Let $Z$ be a minimal cycle and let $D\subset Z$ be a subcomplex homeomorphic
to a 2-disc such that the interior $\rm Int(D)$ is open in $Z$. Denote by
$Z^{\prime}=Z-\rm Int(D)$, the result of deleting the interior of $D$. Then
the 2-complex $Z^{\prime}$ is strongly connected.

###### Proof.

Assume the contrary, i.e. let $Z^{\prime}$ have at least two strongly
connected components $Z^{\prime}_{1},Z^{\prime}_{2},\dots$. Then the quotient
$Z/D$ is homotopy equivalent to the wedge sum of the spaces
$Z^{\prime}_{i}/(Z^{\prime}_{i}\cap D)$ (where $i=1,2,\dots$) and some number
of circles. It is obvious that in the case $Z_{i}^{\prime}\cap D=\partial D$
for some $i$ the complex $Z^{\prime}$ is strongly connected. Thus we may
assume that each intersection $Z_{i}^{\prime}\cap D$ is a proper subcomplex of
the circle $\partial D$, i.e. $Z_{i}^{\prime}\cap D$ is homeomorphic to a
disjoint union of intervals. Hence the quotient
$Z_{i}^{\prime}/(Z_{i}^{\prime}\cap D)$ is homotopy equivalent to the wedge
sum of $Z_{i}^{\prime}$ with several copies of $S^{1}$ which gives
$b_{2}(Z_{i}^{\prime}/(Z_{i}^{\prime}\cap D))=b_{2}(Z_{i}^{\prime})$. Thus we
have

$\displaystyle
b_{2}(Z)=b_{2}(Z/D)=\sum_{i}b_{2}(Z^{\prime}_{i}/(Z^{\prime}_{i}\cap
D))=\sum_{i}b_{2}(Z^{\prime}_{i}).$ (1)

From (1) it follows that among the numbers $b_{2}(Z^{\prime}_{i})$ exactly one
equals 1 and the others vanish. This contradicts the assumption that $Z$ is a
minimal cycle since it contains a proper subcomplex $Z^{\prime}_{i}\subset Z$
with $b_{2}(Z^{\prime}_{i})=1$. ∎

######  Theorem 2.5.

[Classification of minimal cycles] Let $Z$ be a minimal cycle satisfying

$\mu(Z)>1/2.$

Then $Z$ is homeomorphic to one of the following 2-complexes
$Z_{1},Z_{2},Z_{3},Z_{4},$ where $Z_{1}=S^{2}$; $Z_{2}$ is the quotient of
$S^{2}$ with two distinct points identified; $Z_{3}$ is the quotient of
$S^{2}$ with two adjacent arcs identified; and $Z_{4}$ is defined as
$P^{2}\cup\Delta^{2}$, where $\partial\Delta^{2}=P^{2}\cap\Delta^{2}$ equals
the curve $P^{1}\subset P^{2}$.

Figure 3: Minimal cycles $Z_{2}$ (left) and $Z_{3}$ (right).

###### Proof.

Recall that for an edge $e\subset Z$ one denotes by $\deg e$ the degree of
$e$, i.e. the number of faces containing $e$. Using the following formula

$\displaystyle\mu(Z)=\frac{1}{2}+\frac{2\chi(Z)+L(Z)}{2f(Z)},$ (2)

where

$L(X)=\sum_{e}(2-\deg(e)),$

the sum is taken over all edges $e$ of $X$, (see (7), (8) in [6]), we see that
the condition $\mu(Z)>1/2$ translates into

$\displaystyle 2\chi(Z)+L(Z)>0.$ (3)

Note that $L(Z)\leq 0$ since $Z$ is pure and closed. We consider now a few
special cases:

Case A: $L(Z)=0$. Then $Z$ is a pseudo-surface222A pseudo-surface is a
2-complex which is strongly connected and has the property that each edge is
incident to exactly 2 faces. , i.e. each edge has degree 2. The link of every
vertex is a disjoint union of several circles. In other words $Z$ can be
obtained from a connected surface $\tilde{Z}$ by identifying several vertices.
By (3) one has $\chi(Z)>0$ and hence $Z$ is either the sphere $Z_{1}$ or the
sphere with two points identified $Z_{2}$. Hence we see that in the case A the
complex $Z$ is homeomorphic either to $Z_{1}$ or $Z_{2}$.

Case B: $L(Z)=-1$. Let us show that this is impossible. Indeed, in this case
all edges have degree 2 except one edge which has degree 3. If $e$ is this
edge of degree 3 then for one of the incident vertices $v$ one considers the
link of $v$; it is a graph in which all vertices except one have degree 2 and
one vertex has degree 3. This is impossible since the sum of degrees of all
vertices in a graph is always even (as it equals twice the number of edges of
the graph).

If $b_{1}(Z)\geq 1$ then $\chi(Z)\leq 1$ and (3) gives $L(Z)\geq-1$, i.e.
$L(Z)=0$ or $L(Z)=-1$. Thus minimal cycles satisfying $b_{1}(Z)\geq 1$ we are
in one of the cases A or B considered above. We shall assume below that
$b_{1}(Z)=0$.

By Corollary 2.1 the condition $b_{1}(Z)=0$ implies that the link of every
vertex of $Z$ is connected.

The assumptions $b_{2}(Z)=1$ and $b_{0}(Z)=1$ imply $\chi(Z)=2$ and hence
$\mu(Z)>1/2$ is equivalent to $L(Z)\geq-3$. Thus, we have to consider the
following four special cases $L(Z)=0,-1,-2,-3$ with the two first analysed
above.

Case C: $L(Z)=-2$. There are two possibilities: either $Z$ contains two edges
of degree 3 or one edge of degree 4. Consider the first possibility: let
$e,e^{\prime}$ be two edges of degree 3 and let $v$ be a vertex incident to
$e$ but not to $e^{\prime}$. Then the link of $v$ is a graph with all vertices
of degree 2 except one which has degree 3, which is impossible.

Figure 4: Cones.

Now suppose that $Z$ contains an edge $e$ of degree 4 and all other edges of
$Z$ have degree 2. Denote by $v,w$ the endpoints of $e$. The links of $v$ and
$w$ are connected graphs with one vertex of degree 4 and all other vertices of
degree 2. Hence these links are homeomorphic to the figure eight $\Gamma_{8}$
(the wedge sum of two circles). The regular neighbourhood of $v$ is the star
of $v$ which is homeomorphic to the cone over $\Gamma_{8}$. Replacing the cone
$C(\Gamma_{8})$ by the wedge of two cones over the base circles (see Figure 4,
middle) gives a pseudo surface $Z^{\prime}$ on which the original edge $e$ of
degree 4 is represented by two adjacent edges $e_{1},e_{2}$ of degree 2.
Clearly $Z^{\prime}$ is homotopy equivalent to $Z$: indeed, attaching a
triangle to $Z^{\prime}$ as shown on Figure 4 (right) gives a homotopy
equivalent space as the triangle can be collapsed along the free edge; on the
other hand collapsing the whole triangle gives a space homotopy equivalent to
$Z$. By Lemma 2.3 the complex $Z^{\prime}$ is a minimal cycle and therefore it
is strongly connected. Thus, $Z^{\prime}$ is a pseudo-surface with
$b_{1}(Z^{\prime})=0$ and $b_{2}(Z^{\prime})=1$. Using Corollary 2.1 we see
that $Z^{\prime}$ is nonsingular and hence is homeomorphic to $S^{2}$. The
complex $Z$ is obtained from this sphere by folding two adjacent edges
$e_{1},e_{2}$. Thus, $Z$ is homeomorphic to $Z_{3}$.

Case D: $L(Z)=-3$. There are three possibilities: either (1) $Z$ contains one
edge $e$ of degree 5 and all other edges have degree 2, or (2) there are two
edges $e_{1},e_{2}$ with $\deg(e_{1})=3$, and $\deg(e_{2})=4$ and all other
edges have degree $2$, and (3) there are 3 edges $e_{i}$ with $\deg(e_{i})=3$
for $i=1,2,3$ and all other edges of $Z$ have degree 2. In the case (1), if
$v$ is a vertex incident to $e$, then the link of $v$ is a graph with one
vertex of degree $5$ and all other vertices of degree $2$ which is impossible.
Similarly, the case (2) is impossible; one may apply these arguments to the
vertex of $e_{1}$ which is not incident to $e_{2}$. The same reasoning shows
that in the case (3) the only possibility is that the edges
$e_{1},e_{2},e_{3}$ form a triangle.

Below we assume that the edges of degree three $e_{1},e_{2},e_{3}$ form a
triangle with vertices $v_{1},v_{2},v_{3}$, i.e. the edge $e_{1}$ has vertices
$v_{1},v_{2}$, the edge $e_{2}$ has vertices $v_{2},v_{3}$ and $e_{3}$ has
vertices $v_{3},v_{1}$.

Consider the link of $v_{i}$ in complex $Z$. It is a graph with two vertices
of degree three and with all other vertices of degree 2. Hence the link is
homeomorphic to one of the graphs $\Gamma_{1},\Gamma_{2}$ shown on Figure 5.

Figure 5: Possible links of $v_{i}$.

Let us show that the graph $\Gamma_{1}$ is in fact impossible. Indeed, suppose
that the link of $v_{i}$ is homeomorphic to $\Gamma_{1}$. The arc connecting
two triple points of $\Gamma_{1}$ corresponds to a sequence of 2-faces
$\sigma_{1},\dots,\sigma_{r}$ such that $\sigma_{j}\cap\sigma_{j+1}$ is an
edge containing $v_{i}$. The union $\sigma=\sigma_{1}\cup\dots\cup\sigma_{r}$
is a subcomplex homeomorphic to a disc. Consider $Z^{\prime}=Z-\rm
Int(\sigma)$. By Lemma 2.4, the complex $Z^{\prime}$ is strongly connected. We
have $\chi(Z^{\prime})=1$ and $b_{2}(Z^{\prime})=0$ and hence
$b_{1}(Z^{\prime})=0$. This contradicts Corollary 2.1 since the link of
$v_{i}$ in $Z^{\prime}$ has two connected components.

Suppose that there is a 2-simplex $\sigma$ in $Z$ having the vertices
$v_{1},v_{2},v_{3}$. Then removing the interior of this simplex we obtain a
pseudo surface $Z^{\prime}$ (i.e. $L(Z^{\prime})=0$) with
$b_{1}(Z^{\prime})=b_{2}(Z^{\prime})=0$. By Lemma 2.4, the complex
$Z^{\prime}$ must be strongly connected. Then ${\rm{Sing}}(v)=0$ for every
vertex $v\in Z^{\prime}$, since otherwise $b_{1}(Z^{\prime})>0$, see Corollary
2.1. Hence $Z^{\prime}$ is a genuine closed surface and since we know the
Betti numbers of $Z^{\prime}$, clearly $Z^{\prime}$ must be homeomorphic to
the real projective plane. Thus $Z$ is homeomorphic to the union of $P^{2}$
and a triangle $\Delta^{2}$. The intersection $P^{2}\cap\Delta^{2}$ is a
simple closed curve. If this curve is null-homologous on $P^{2}$ then this
curve must separate $P^{2}$ into two connected components one of which must be
homeomorphic to a 2-disc and together with $\Delta^{2}$ this disc would form
proper a 2-cycle in $Z$ contradicting the minimality of $Z$ (see Definition
2.2). Hence, the curve $P^{2}\cap\Delta^{2}$ is homologous to $P^{1}\subset
P^{2}$. Therefore $Z$ is homeomorphic to $Z_{4}$.

Next we consider the case that there is no 2-simplex with sides
$e_{1},e_{2},e_{3}$. Let us label the three 2-faces incident to $e_{1}$ by the
symbols $1,2,3$. In the link of $v_{2}$ the edge $e_{1}$ corresponds to one of
the vertices of degree three and the symbols $1,2,3$ are now associated with
the three arcs (see the graph $\Gamma_{2}$ on Figure 5) incident to this
vertex. Viewing the other triple point of the link of $v_{2}$ we obtain a
labelling by the symbols $1,2,3$ of the three triangles incident to the edge
$e_{1}$. Thus we see that a labelling by the symbols $1,2,3$ of the three
triangles containing an edge $e_{i}$ determines a labelling of the following
edge $e_{i+1}$. Performing this process in the following sequence $e_{1}\to
e_{2}\to e_{3}\to e_{1}$ we obtain a permutation $\tau$ of the symbols
$1,2,3$. We denote by $k\,(=1,2,3)$ the number of orbits of the action of
$\tau$ on $\\{1,2,3\\}$.

Case D1: Suppose that $k=1$. Let $c=\sum_{j}n_{j}\sigma_{j}$ be a nontrivial
2-cycle of $Z$ with integral coefficients $n_{j}$; here the symbols
$\sigma_{i}$ denote distinct oriented simplexes of $Z$. Due to our minimality
assumption, $n_{i}\not=0$ for any $i$. If two simplexes $\sigma_{i}$ and
$\sigma_{i^{\prime}}$ have a common edge of degree two then $n_{i}=\pm
n_{i^{\prime}}$. The complement $Z-E$ (where $E$ is the union of the triple
edges $e_{1},e_{2},e_{3}$) is strongly-connected since $Z$ is strongly
connected and $k=1$, i.e. one may pass from any face incident to $E$ to any
other face incident to $E$ by jumping across edges not in $E$. Thus, any two
2-simplexes $\sigma,\sigma^{\prime}$ of $Z$ can be connected by a chain
$\sigma=\sigma_{1},\sigma_{2},\dots,\sigma_{r}=\sigma^{\prime}$ such that each
$\sigma_{i}$ and $\sigma_{i+1}$ have a common edge of degree two. Hence we
obtain that $n_{i}=\pm n_{j}$ for any $i,j$. This leads to a contradiction
with $\partial c=0$ since near an edge $e_{r}$ of degree three we will have
three 2-simplexes, each contribution the same amount, up to a sign. Thus, Case
D1 is impossible.

Case D2: Suppose that $k=2$ or $k=3$. Then near the union of the triple edges
$E$ the complex $Z$ is homeomorphic either to $Y\times S^{1}$ (where $Y$ is
the graph representing the letter Y) or to the union of the Möbius band $M$
and the cylinder $N=[0,1]\times S^{1}$ such that $M\cap N=0\times S^{1}$ is
the central circle of the Möbius band. In either case we may cut $Z$ along the
triple circle $E$, separating a cylinder from the rest, such that the result
is a surface $\hat{Z}$ with boundary. Points of $E$ will be represented on
$\hat{Z}$ by two circles, one being the base of the cylindrical part and
another the middle circle of a cylinder or a Möbius band. If $\hat{Z}$ is
connected then it is homotopy equivalent to a graph and hence
$\chi(\hat{Z})=\chi(Z)\leq 1$. Since $L(Z)=-3$, we see that (3) is violated.
Therefore the surface $\hat{Z}$ must have two connected components
$\hat{Z}_{1}\sqcup\hat{Z}_{2}$, one of which (say, $\hat{Z}_{1}$) is a closed
surface, while the other $\hat{Z}_{2}$ has one boundary circle. The minimality
condition implies that the closed surface $\hat{Z}_{1}$ must be non-
orientable. Thus we have
$2=\chi(Z)=\chi(\hat{Z})=\chi(\hat{Z}_{1})+\chi(\hat{Z}_{2})$ and
$\chi(\hat{Z}_{1})\leq 1$, $\chi(\hat{Z}_{2})\leq 1$ which implies that
$\chi(\hat{Z}_{1})=1=\chi(\hat{Z}_{2})$. Therefore, $\hat{Z}_{1}$ is the real
projective plane and $\hat{Z}_{2}$ is a disk. We obtain that $Z$ is the union
of the projective plane and a disk intersecting along the triangle $E$.
Clearly $E$ is not null-homologous in $\hat{Z}_{1}$ (since otherwise it would
cut the projective plane into two connected components one of which would be
orientable and together with $\hat{Z}_{2}$ it would make a cycle,
contradicting minimality of $Z$).

Clearly the pair $(\hat{Z}_{1},E)$ is homeomorphic to $(P^{2},P^{1})$, and $Z$
is homeomorphic to $Z_{4}$.

This completes the proof. ∎

######  Corollary 2.6.

In any minimal cycle $Z$ with $\mu(Z)>1/2$ there exists a 2-face $\sigma$ such
that the boundary curve $\partial\sigma$ is null-homotopic in the complement
$Z-\rm Int(\sigma)$.

######  Lemma 2.7.

Let $X$ be a finite closed strongly connected pure 2-complex with
$b_{2}(X)=0$. Then either $\mu(X)\leq 1/2$ or $X$ is homeomorphic to the
projective plane ${\bf RP}^{2}$.

###### Proof.

Assume that $\mu(X)>1/2$; this is equivalent (using formula (2)) to

$\displaystyle{\mathcal{L}}(X)\equiv 2\chi(X)+L(X)=2-2b_{1}(X)+L(X)>0.$ (4)

Besides, we have $L(X)\leq 0$, since $X$ is closed. The inequality (4) implies
that $L(X)$ can be either $-1$ or $0$. In the proof of Theorem 2.5 (see Case
B) we showed that $L(X)=-1$ is impossible. Hence, $L(X)=0$, i.e. $X$ is a
pseudo-surface. Inequality (4) now implies that $b_{1}(X)=0$. Using Corollary
2.1 we obtain that $X$ is a genuine surface without singularities. Thus $X$ is
a compact nonorientable surface with $b_{1}(X)=0$, i.e. $X$ is homeomorphic to
the projective plane. ∎

We shall say that a 2-complex $X$ is an iterated wedge of projective planes if
it can be represented as a union of subcomplexes $X=\cup_{i=1}^{n}A_{i}$ where
each $A_{j}$ is homeomorphic to a projective plane and the intersection

$A_{j}\cap(\cup_{i=1}^{j-1}A_{i})$

is a single point set for $j=1,\dots,n$.

######  Lemma 2.8.

Let $X$ be a finite pure connected 2-complex with $b_{1}(X)=0$. Then $X$ is
iterated wedge of its strongly connected components.

###### Proof.

We shall use the following remark. Let $A\cup B=X$ be two connected
subcomplexes which are unions of strongly connected components of $X$ and such
that every strongly connected component of $X$ is contained either in $A$ or
in $B$ but not in both $A$ and $B$. Then the intersection $A\cap B$ is a
finite set of vertices and using $b_{1}(X)=0$ in the Mayer - Vietoris sequence
implies that $\tilde{H}_{0}(A\cap B)=0$, i.e. $A\cap B$ is a single point.

Let $A_{1}$ be a strongly connected component of $X$. Using the connectedness
of $X$ and the previous remark, we may find another strongly connected
component $A_{2}$ of $X$ such that $A_{1}\cap A_{2}$ is a single point.
Inductively, we may find a sequence $A_{1},\dots,A_{r}$ of strongly connected
components of $X$ such that $X=A_{1}\cup\dots\cup A_{r}$ and for any $j$ the
intersection

$A_{j}\cap(\cup_{i=1}^{j-1}A_{i})$

is a single point. Hence $X$ is an iterated wedge of its strongly connected
components. ∎

A version of Lemma 2.7 with the words “strongly connected” replaced by
“connected” reads as follows.

######  Lemma 2.9.

Let $X$ be a finite closed connected pure 2-complex with $b_{2}(X)=0$ and
$\mu(X)>1/2$. Then $X$ is homeomorphic to an iterated wedge of projective
planes.

###### Proof.

We will use induction on the number of strongly connected components $k$ of
$X$. Lemma 2.7 covers the case $k=1$. Assume now that Lemma 2.9 has been
proven for all complexes $X$ with less than $k$ strongly connected components.

If $X$ has $k$ strongly connected components and $b_{2}(X)=0$, $\mu(X)>1/2$
then $b_{1}(X)=0$ (as follows from the inequality (3) combined with $L(X)\leq
0$). By Lemma 2.8, $X$ can be represented as a wedge (one-point-union)
$X=A\vee B$ with $A$ strongly connected and $B$ having $k-1$ strongly
connected components. The complexes $A$ and $B$ are pure, closed, connected
and $b_{2}(A)=0=b_{2}(B)$. One has $L(X)=L(A)+L(B)$ and
$\chi(X)=\chi(A)+\chi(B)-1$ which imply (using the notation introduced in the
proof of Lemma 2.7)

$\mathcal{L}(X)=\mathcal{L}(A)+\mathcal{L}(B)-2.$

We know by the induction hypothesis that either $\mathcal{L}(A)\leq 0$, or $A$
is homeomorphic to the projective plane and then $\mathcal{L}(A)=2$. Besides,
either $\mathcal{L}(B)\leq 0$ or $B$ is an iterated wedge of projective planes
and then $\mathcal{L}(B)=2$. Thus, we see that either $\mathcal{L}(X)\leq 0$
(which is equivalent to $\mu(X)\leq 1/2$ and contradicts our assumption
$\mu(X)>1/2$) or $\mathcal{L}(X)=2$ and $X$ is an iterated wedge of projective
planes. ∎

######  Corollary 2.10.

[Compare with Lemma 4.1 from [2]] Let $Z$ be a connected 2-complex with
$\tilde{\mu}(Z)>1/2$. Then $Z$ is homotopy equivalent to a wedge of circles,
spheres and projective planes.

###### Proof.

Without loss of generality we may additionally assume that $Z$ is strongly
connected since otherwise $Z$ is homotopy equivalent to a wedge sum of its
strongly connected components and a number of circles. Besides, we may assume
that $Z$ is closed, $\partial Z=\emptyset$ (otherwise, we may perform a
sequence of collapses to obtain a closed subcomplex $Z^{\prime}\subset Z$
having the same homotopy type). Similarly, without loss of generality we may
assume that $Z$ is pure since otherwise we can apply the arguments given below
to its pure part.

We shall act by induction on $b_{2}(Z)$.

If $b_{2}(Z)=0$ and $\tilde{\mu}(Z)>1/2$ then using Lemma 2.9 we see that the
complex $Z$ is homotopy equivalent to a wedge of circles and projective
planes.

Assume that Corollary 2.10 was proven for all connected 2-complexes $Z$
satisfying $\tilde{\mu}(Z)>1/2$ and $b_{2}(Z)<k$.

Consider a 2-complex $Z$ satisfying $b_{2}(Z)=k>0$ and $\tilde{\mu}(Z)>1/2$.
Find a minimal cycle $Z^{\prime}\subset Z$. Then the homomorphism
$H_{2}(Z^{\prime};{\mathbf{Z}})={\mathbf{Z}}\to H_{2}(Z;{\mathbf{Z}})$ is an
injection. Let $\sigma\subset Z^{\prime}$ be a simplex given by Corollary 2.6.
Then $Z^{\prime\prime}=Z-\rm Int(\sigma)$ satisfies
$b_{2}(Z^{\prime\prime})=k-1$. Indeed, in the exact sequence

$0\to H_{2}(Z^{\prime\prime})\to H_{2}(Z)\to
H_{2}(Z,Z^{\prime\prime})\,(={\mathbf{Z}})\stackrel{{\scriptstyle\partial_{\ast}}}{{\to}}H_{1}(Z^{\prime\prime})\to\dots$

the homomorphism $\partial_{\ast}=0$ is trivial since the curve
$\partial\sigma$ is null-homotopic in $Z^{\prime\prime}$. Since
$\tilde{\mu}(Z^{\prime\prime})>1/2$, by induction hypothesis
$Z^{\prime\prime}$ is homotopy equivalent to a wedge of spheres, circles and
projective planes. Then $Z\simeq Z^{\prime\prime}\vee S^{2}$ also has this
property. ∎

##  3 Isoperimetric constants of simplicial complexes

Let $X$ be a finite simplicial 2-complex. For a simplicial loop
$\gamma:S^{1}\to X^{(1)}\subset X$ we denote by $|\gamma|$ the length of
$\gamma$. If $\gamma$ is null-homotopic, $\gamma\sim 1$, we denote by
$A_{X}(\gamma)$ the area of $\gamma$, i.e. the minimal number of triangles in
any simplicial filling $V$ for $\gamma$. A simplicial filling (or a simplicial
Van Kampen diagram) for a loop $\gamma$ is defined as a pair of simplicial
maps $S^{1}\stackrel{{\scriptstyle i}}{{\to}}V\stackrel{{\scriptstyle
b}}{{\to}}X$ such that $\gamma=b\circ i$ and the mapping cylinder of $i$ is a
disc with boundary $S^{1}\times 0$, see [2].

Note that for $X\subset Y$ and $\gamma:S^{1}\to X$, $\gamma\sim 1$, one has
$A_{X}(\gamma)\geq A_{Y}(\gamma).$

Define the following invariant of $X$

$I(X)=\inf\left\\{\frac{|\gamma|}{A_{X}(\gamma)};\quad\gamma:S^{1}\to
X^{(1)},\gamma\sim 1\quad\mbox{in $X$}\right\\}\,\in\,{\mathbf{R}}.$

The inequality $I(X)\geq a$ means that for any null-homotopic loop $\gamma$ in
$X$ one has the isoperimetric inequality $A_{X}(\gamma)\leq
a^{-1}\cdot|\gamma|$. The inequality $I(X)<a$ means that there exists a null-
homotopic loop $\gamma$ in $X$ with $A_{X}(\gamma)>a^{-1}\cdot|\gamma|$, i.e.
$\gamma$ is null-homotopic but does not bound a disk of area less than
$a^{-1}\cdot|\gamma|$.

It is well known that $I(X)>0$ if and only if $\pi_{1}(X)$ is hyperbolic in
the sense of M. Gromov [9].

######  Example 3.1.

For $X=T^{2}$ one has $I(X)=0$.

######  Example 3.2.

Let $X$ be a finite 2-complex satisfying $\tilde{\mu}(X)>1/2$. Then by
Corollary 2.10 the fundamental group $\pi_{1}(X)$ is a free product of several
copies of ${\mathbf{Z}}$ and ${\mathbf{Z}}_{2}$ and is hyperbolic. Hence
$I(X)>0$, compare Theorem 6.2 below.

######  Remark 3.3.

Suppose that $\gamma=\gamma_{1}\cdot\gamma_{2}$ is the concatenation of two
null-homotopic loops $\gamma_{1}$, $\gamma_{2}$ in $X$. Then

$|\gamma|=|\gamma_{1}|+|\gamma_{2}|,\quad\mbox{and}\quad A_{X}(\gamma)\leq
A_{X}(\gamma_{1})+A_{X}(\gamma_{2}).$

This implies that

$\frac{|\gamma|}{A_{X}(\gamma)}\geq\frac{|\gamma_{1}|+|\gamma_{2}|}{A_{X}(\gamma_{1})+A_{X}(\gamma_{2})}\geq\min\left\\{\frac{|\gamma_{1}|}{A_{X}(\gamma_{1})},\frac{|\gamma_{2}|}{A_{X}(\gamma_{2})}\right\\}$

and leads to the following observation:

The number $I(X)$ coincides with the infimum of the ratios
${|\gamma|}\cdot{A_{X}(\gamma)}^{-1}$ where $\gamma$ runs over all null-
homotopic simplicial prime loops in $X$, i.e. such that their lifts to the
universal cover $\tilde{X}$ of $X$ are simple. Note that any simplicial
filling $S^{1}\stackrel{{\scriptstyle i}}{{\to}}V\stackrel{{\scriptstyle
b}}{{\to}}X$ for a prime loop $\gamma:S^{1}\to X$ has the property that $V$ is
a simplicial disc and $i$ is a homeomorphism $i:S^{1}\to\partial V$. Hence for
prime loops $\gamma$ the area $A_{X}(\gamma)$ coincides with the minimal
number of 2-simplexes in any simplicial spanning disc for $\gamma$.

The following Theorem 3.4 gives a uniform isoperimetric constant for random
complexes $Y\in Y(n,p)$. It is a slightly stronger statement than simply
hyperbolicity of the fundamental group of $Y$. Theorem 3.4 is implicitly
contained in [2] although it was not stated there explicitly.

######  Theorem 3.4.

Suppose that for some $\epsilon>0$ the probability parameter $p$ satisfies

$\displaystyle p\ll n^{-1/2-\epsilon}.$ (5)

Then there exists a constant $c_{\epsilon}>0$ depending only on $\epsilon$
such that a random 2-complex $Y\in Y(n,p)$, with probability tending to 1 as
$n\to\infty$, has the following property: any subcomplex $Y^{\prime}\subset Y$
satisfies $I(Y^{\prime})\geq c_{\epsilon}$ and in particular, the fundamental
group $\pi_{1}(Y^{\prime})$ is hyperbolic.

We give a detailed proof of Theorem 3.4 in the Appendix.

We state now two immediate corollaries of Theorem 3.4.

######  Corollary 3.5.

Under the assumption (5), a random 2-complex $Y\in Y(n,p)$ contains no
subcomplexes homeomorphic to the torus $T^{2}$, a.a.s.

###### Proof.

By Example 3.1 any torus $S$ satisfies $I(S)=0$ and the inclusion $S\subset Y$
would contradict Theorem 3.4. ∎

######  Corollary 3.6.

Under the assumption (5), a random 2-complex $Y\in Y(n,p)$ contains no
subcomplex having more than $2\epsilon^{-1}$ faces which is homeomorphic to
the sphere $S^{2}$, a.a.s.

###### Proof.

Suppose that a random 2-complex $Y\in Y(n,p)$ contains a sphere $S\subset Y$
as a subcomplex.

Firstly we show that the number of faces $f(S)$ is bounded above by a constant
depending on $\epsilon$. Indeed, removing a 2-simplex from $S$ gives a disc
$S^{\prime}$ and by Theorem 3.4 the isoperimetric ratio of the boundary curve
$\gamma$ of this disc must satisfy

$\frac{|\gamma|}{A_{S^{\prime}}(\gamma)}=\frac{3}{f(S)-1}\geq c_{\epsilon}$

where $c_{\epsilon}>0$ is the constant of Theorem 3.4. Thus we obtain

$\displaystyle f(S)\leq 3\cdot c_{\epsilon}^{-1}+1.$ (6)

Secondly, we observe that there are finitely many isomorphism types of
triangulations of the sphere $S^{2}$ satisfying (6) and we therefore may apply
Theorem 15 from [5] or Lemma 1.1. By Theorem 27 and formula (8) from [5] we
obtain $\tilde{\mu}(S)=\frac{1}{2}+\frac{2}{f(S)}.$ If
$\tilde{\mu}(S)<1/2+\epsilon$ then (by Lemma 1.1) $S$ cannot be embedded into
a random 2-complex $Y\in Y(n,p)$, a.a.s. Hence, for the triangulated spheres
$S$ embeddable into $Y$ (a.a.s.) we must have
$\tilde{\mu}(S)=\frac{1}{2}+\frac{2}{f(S)}\geq\frac{1}{2}+\epsilon,$ implying
$f(S)\leq 2\cdot\epsilon^{-1}$. ∎

Let $X$ be a simplicial 2-complex. By $\rm{sys}(X)$ we denote the systole of
$X$, which is defined as the length of the shortest homotopically nontrivial
simplicial loop in $X$. By Theorem 1.3 from [11] (see also Theorem 6.7.A from
[8]) one has

$\displaystyle{\rm{sys}}(X)<6\cdot A(X)^{1/2},$ (7)

assuming that the fundamental group of $X$ is not a free group. Here $A(X)$
denotes the number of $2$-simplexes in $X$. To deduce (7) from [11], Theorem
1.3 we apply this theorem to $X$ equipped with a piecewise flat metric $g$ in
which each edge has length 1 and each 2-simplex has area $\sqrt{3}/4$. Let
${\rm{sys}}_{g}(X)$ and $A_{g}(X)$ denote the systole and the area of $X$ with
respect to this metric. Then $A_{g}(X)=A(X)\cdot\sqrt{3}/4$ and elementary
estimates show that

${\rm{sys}}_{g}(X)\leq{\rm{sys}}(X)\leq 2\cdot{\rm{sys}}_{g}(X).$

Hence,

$\frac{{\rm{sys}}^{2}(X)}{A(X)}\leq\frac{\sqrt{3}\left({\rm{sys}}_{g}(X)\right)^{2}}{A_{g}(X)}\leq\sqrt{3}\cdot
12<36$

which implies (7).

######  Corollary 3.7.

Under the assumption (5), a random 2-complex $Y\in Y(n,p)$ contains no
subcomplex having more than $\epsilon^{-1}$ faces which is homeomorphic to the
projective plane ${\mathbf{RP}}^{2}$, a.a.s.

###### Proof.

Suppose that a random 2-complex $Y\in Y(n,p)$ contains a subcomplex $P\subset
Y$ homeomorphic to the projective plane. By Theorem 3.4 the isoperimetric
constant $I(P)$ satisfies $I(P)\geq c_{\epsilon}$. Consider the simple
simplicial curve $\gamma$ in $P$ which is not null-homotopic and has length
equal to ${\rm{sys}}(P)$. The twice passed curve $\gamma$ is null-homotopic in
$P$ and the area of $\gamma^{2}$ equals $A(P)$. Thus we have

$\displaystyle\frac{2{\rm{sys}}(P)}{A(P)}\geq c_{\epsilon}.$ (8)

Applying (7) we obtain ${\rm{sys}}(P)^{2}\leq 36\cdot A(P)$ and combining with
(8) we get $A(P)\leq 144\cdot c_{\epsilon}^{-2}$.

There are finitely many isomorphism types of triangulations of the real
projective plane ${\mathbf{RP}}^{2}$ with at most $144c_{\epsilon}^{-2}$
faces. By Theorem 27 and formula (8) from [5] we obtain
$\tilde{\mu}(S)=\frac{1}{2}+\frac{1}{f(S)}.$ If $\tilde{\mu}(S)<1/2+\epsilon$
then (by Lemma 1.1) $S$ cannot be embedded into a random 2-complex $Y\in
Y(n,p)$, a.a.s. Hence, for the triangulated real projective plane $S$
embeddable into $Y$ (a.a.s.) we must have
$\tilde{\mu}(S)=\frac{1}{2}+\frac{1}{f(S)}\geq\frac{1}{2}+\epsilon,$ implying
$f(S)\leq\epsilon^{-1}$. ∎

##  4 Torsion in fundamental groups of random 2-complexes

One of the main results of this section is Theorem 4.5 which states that the
fundamental group of a random 2-complex has a nontrivial element of order $2$
assuming that $n^{-3/5}\ll p\ll n^{-1/2-\epsilon}$. The proof of Theorem 4.5
uses Theorem 3.4 together with Theorem 4.3 which is stated and proven below.

The second main result presented in this section is Theorem 4.6 which claims
that for any odd prime $m\geq 3$ (assuming that $p\ll n^{-1/2-\epsilon}$) the
fundamental group of any subcomplex $Y^{\prime}\subset Y$ of a random complex
$Y\in Y(n,p)$ has no $m$-torsion, a.a.s. The proof uses Theorem 3.4 as well as
the inequalities for systoles of Moore surfaces.

###  4.1 The numbers of embeddings

Consider two 2-complexes $S_{1}\supset S_{2}$. Denote by $v_{i}$ and $f_{i}$
the numbers of vertices and faces of $S_{i}$. We have $v_{1}\geq v_{2}$ and
$f_{1}\geq f_{2}$. We will assume that $f_{1}>f_{2}$.

Let $\mu(S_{1},S_{2})$ denote the ratio

$\mu(S_{1},S_{2})=\frac{v_{1}-v_{2}}{f_{1}-f_{2}}.$

If $\mu(S_{1})<\mu(S_{2})$ then

$\displaystyle\mu(S_{1},S_{2})<\mu(S_{1})<\mu(S_{2}).$ (9)

If $\mu(S_{1})>\mu(S_{2})$ then

$\displaystyle\mu(S_{1},S_{2})>\mu(S_{1})>\mu(S_{2}).$ (10)

These two observations can be summarised by saying that $\mu(S_{1})$ always
lies in the interval connecting $\mu(S_{2})$ and $\mu(S_{1},S_{2})$.

One has the following formula

$\displaystyle\mu(S_{1},S_{2})=\frac{1}{2}+\frac{2(\chi(S_{1})-\chi(S_{2}))+L(S_{1})-L(S_{2})}{2(f_{1}-f_{2})},$
(11)

which follows from the equation $2v_{i}=f_{i}+2\chi(S_{i})+L(S_{i})$; the
latter is equivalent to (2).

######  Remark 4.1.

Let $S_{2}$ be a pseudo-surface and $2\chi(S_{1},S_{2})+L(S_{1})<0$. Then
$\mu(S_{1},S_{2})<1/2$.

Note that $L(S_{2})=0$ since $S_{2}$ is a pseudo-surface. This remark applies
to the case when $S_{1}$ is a union of a pseudo-surface $S_{2}$ and a number
of simplicial discs.

######  Theorem 4.2.

Let $S_{1}\supset S_{2}$ be two fixed 2-complexes and333The assumption (12) is
meaningful iff $\mu(S_{1},S_{2})<\tilde{\mu}(S_{2})\leq\mu(S_{2})$ which, as
follows from (9) and (10), implies that $\mu(S_{1})<\mu(S_{2})$. Thus, if
Theorem 4.2 is applicable, then $\mu(S_{1})<\mu(S_{2})$.

$\displaystyle n^{-\tilde{\mu}(S_{2})}\ll p\ll n^{-\mu(S_{1},S_{2})}.$ (12)

Then the number of simplicial embeddings of $S_{1}$ into a random 2-complex
$Y\in Y(n,p)$ is smaller than the number of simplicial embeddings of $S_{2}$
into $Y$, a.a.s. In particular, under the assumptions (12), with probability
tending to one, there exists a simplicial embedding $S_{2}\to Y$ which does
not extend to an embedding $S_{1}\to Y$.

###### Proof.

Let $X_{i}:Y(n,p)\to{\mathbf{Z}}$ be the random variable counting the number
of simplicial embeddings of $S_{i}$ into $Y\in Y(n,p)$, $i=1,2$. We know that

$\mathbb{E}(X_{i})=\binom{n}{v_{i}}v_{i}!p^{f_{i}}\sim n^{v_{i}}p^{f_{i}}.$

Our goal is to show that $X_{1}<X_{2}$, a.a.s. The left hand side inequality
(12) implies (via Theorem 15 from [5]) that $X_{2}(Y)>0$, a.a.s., i.e. $S_{2}$
admits an embedding into $Y$ with probability tending to one. We have

$\frac{\mathbb{E}(X_{1})}{\mathbb{E}(X_{2})}\sim
n^{v_{1}-v_{2}}p^{f_{1}-f_{2}}=\left[n^{\mu(S_{1},S_{2})}p\right]^{f_{1}-f_{2}}\to
0$

tends to zero, under our assumption (12) (the right hand side).

Below we shall find $t_{1},t_{2}>0$ such that

$t_{1}+t_{2}=\mathbb{E}(X_{2})-\mathbb{E}(X_{1})$

and $\mathbb{E}(X_{1})/t_{1}\to 0$ while $\mathbb{E}(X_{2})/t_{2}$ is bounded.

One of the following three statements holds: either $X_{1}<X_{2}$ or
$X_{1}\geq\mathbb{E}(X_{1})+t_{1}$ or $X_{2}<\mathbb{E}(X_{2})-t_{2}$ and
therefore

$\displaystyle P(X_{1}<X_{2})\geq
1-P(X_{1}\geq\mathbb{E}(X_{1})+t_{1})-P(X_{2}<\mathbb{E}(X_{2})-t_{2}).$ (13)

By Markov’s inequality

$P(X_{1}\geq\mathbb{E}(X_{1})+t_{1})\leq\frac{\mathbb{E}(X_{1})}{\mathbb{E}(X_{1})+t_{1}}=\frac{\frac{\mathbb{E}(X_{1})}{t_{1}}}{1+\frac{\mathbb{E}(X_{1})}{t_{1}}}\to
0$

while by Chebyschev’s inequality

$P(X_{2}<\mathbb{E}(X_{2})-t_{2})<\frac{{\rm{Var(X_{2})}}}{t_{2}^{2}}.$

It is known (see [5], proof of Theorem 15) that under our assumptions (12) the
ratio $\frac{{\rm{Var(X_{2})}}}{\mathbb{E}(X_{2})^{2}}$ tends to zero.
Therefore combining the last two inequalities with the inequality (13) we see
that $P(X_{1}<X_{2})$ tends to 1 as $n\to\infty$.

To make a specific choice of $t_{1}$ and $t_{2}$ one may take
$t_{1}=\sqrt{\mathbb{E}(X_{1})\mathbb{E}(X_{2})}$ and
$t_{2}=\mathbb{E}(X_{2})-\mathbb{E}(X_{1})-t_{1}$. Then

$\frac{\mathbb{E}(X_{1})}{t_{1}}=\sqrt{\frac{\mathbb{E}(X_{1})}{\mathbb{E}(X_{2})}}\to
0$

and

$\frac{\mathbb{E}(X_{2})}{t_{2}}=\frac{1}{1-\frac{\mathbb{E}(X_{1})}{\mathbb{E}(X_{2})}-\sqrt{\frac{\mathbb{E}(X_{1})}{\mathbb{E}(X_{2})}}}\to
1$

is bounded. This completes the proof. ∎

######  Theorem 4.3.

Let

$T_{j}\supset S,\quad j=1,\dots,N,$

be a finite family of 2-complexes containing a given 2-complex $S$ and
satisfying $\mu(T_{j})<\mu(S)$. Assume that

$\displaystyle n^{-\tilde{\mu}(S)}\ll p\ll n^{-\mu(T_{j},S)},\quad\mbox{for
any}\quad j=1,\dots,N.$ (14)

Then, with probability tending to one, for a random 2-complex $Y\in Y(n,p)$
there exists a simplicial embedding $S\to Y$ which does not extend to a
simplicial embedding $T_{j}\to Y$, for any $j=1,\dots,N$.

###### Proof.

Let $X_{1,j}:Y(n,p)\to{\mathbf{Z}}$ denote the random variable counting the
number of embeddings of $T_{j}$ into $Y\in Y(n,p)$. Denote
$X_{1}=\sum_{j=1}^{N}X_{1,j}.$ Besides, let $X_{2}:Y(n,p)\to{\mathbf{Z}}$
denote the number of embeddings of $S$ into a random 2-complex $Y\in Y(n,p)$.
As in the proof of the provious theorem one has

$\frac{\mathbb{E}(X_{1})}{\mathbb{E}(X_{2})}=\sum_{j=1}^{N}\frac{\mathbb{E}(X_{1,j})}{\mathbb{E}(X_{2})}\to
0$

thanks to our assumption (14) (the right hand side inequality). Taking
$t_{1}=\sqrt{\mathbb{E}(X_{1})\mathbb{E}(X_{2})}$ and
$t_{2}=\mathbb{E}(X_{2})-\mathbb{E}(X_{1})-t_{1}$ (as in the proof of the
previous theorem) one has $t_{1}+t_{2}=\mathbb{E}(X_{2})-\mathbb{E}(X_{1})$
and $\mathbb{E}(X_{1})/t_{1}\to 0$ while $\mathbb{E}(X_{2})/t_{2}$ is bounded.
Repeating the arguments used in the proof of the previous theorem we see that
$X_{1}<X_{2}$, a.a.s. Since every embedding $T_{j}\to Y$ determines (by
restriction) an embedding $S\to Y$, the inequality $X_{1}(Y)<X_{2}(Y)$ implies
that there there are embeddings $S\to Y$ which admit no extensions to an
embedding $T_{j}\to Y$, for any $j=1,\dots,N$. ∎

###  4.2 Projective planes in random 2-complexes

In this section we prove the existence of 2-torsion in fundamental groups of
random 2-complexes, see Theorem 4.5. The proof uses simplical embeddings of
projective planes into random 2-complexes. Note that for a triangulation $X$
of the real projective plane one has

$\mu(X)=1/2+\frac{1}{f(X)},$

where $f(X)$ is the number of faces of $X$, see (2), and therefore the maximal
value of $\mu(X)$ happens when $f(X)$ is minimal.

It is well known that the complex $S$ shown in the Figure 6 is the minimal
triangulation of $P^{2}$; it has 10 faces and therefore $\mu(S)=3/5$. Moreover
$\tilde{\mu}(S)=\mu(S)=3/5$ by Theorem 27 from [5]. By Lemma 1.1 for $p\gg
n^{-3/5}$ the complex $S$ embeds into a random 2-complex, a.a.s. This explains
the appearance of the exponent $3/5$ in Theorem 4.5 below.

Figure 6: Minimal triangulation of the real projective plane; the antipodal
points on the peripheral hexagon must be identified.

We may mention here that for $p\ll n^{-3/5}$ the fundamental group of a random
2-complex $Y\in Y(n,p)$ is torsion free, see Corollary 5.9.

######  Definition 4.4.

A subcomplex $S\subset Y$ is said to be essential if the induced homomorphism
$\pi_{1}(S)\to\pi_{1}(Y)$ is injective.

######  Theorem 4.5.

Let $S$ be a triangulation of the real projective plane ${\mathbf{RP}}^{2}$
having 6 vertices, 15 edges and 10 faces. Assume that $\epsilon>0$ and

$n^{-3/5}\ll p\ll n^{-1/2-\epsilon}.$

Then a random 2-complex $Y\in Y(n,p)$ contains $S$ as an essential subcomplex,
a.a.s. In particular, the fundamental group $\pi_{1}(Y)$ contains an element
of order two and hence its cohomological dimension is infinite.

###### Proof.

Consider the set $\mathcal{S}_{\epsilon}$ of isomorphism types of pure
connected closed 2-complexes $X$ satisfying the following conditions:

  1. (a)

$X$ contains $S$ as a subcomplex;

  2. (b)

The inclusion $S\to X$ induces a trivial homomorphism
$\pi_{1}(S)\to\pi_{1}(X)$;

  3. (c)

For any subcomplex $S\subset X^{\prime}\subset X$, $X^{\prime}\not=X$, the
homomorphism $\pi_{1}(S)\to\pi_{1}(X^{\prime})$ is nontrivial;

  4. (d)

$X$ has at most $10+3c_{\epsilon}^{-1}$ faces where $c_{\epsilon}$ is the
constant given by Theorem 3.4;

  5. (e)

$\tilde{\mu}(X)>1/2+\epsilon$;

Let us show that any $X\in{\mathcal{S}}_{\epsilon}$ is homeomorphic to the
complex $Z_{4}$, as defined in Theorem 2.5. In the exact sequence

$0\to H_{2}(X)\to H_{2}(X,S)\to H_{1}(S)={\mathbf{Z}}_{2}\to 0$

the middle group has no torsion and hence $b_{2}(X)=b_{2}(X,S)\geq 1$. If
$Z\subset X$ is a minimal cycle then $\mu(Z)>1/2+\epsilon$ (by (e)) and
Theorem 2.5 implies that $Z$ is homeomorphic to one of the 2-complexes
$Z_{1},Z_{2},Z_{3},Z_{4}$.

If $Z$ is homeomorphic to one of the complexes $Z_{1},Z_{2},Z_{3}$ then any
face $\sigma\subset Z$ satisfies the conditions of Corollary 2.6. Therefore
removing from $X$ any face $\sigma\subset Z-S$ would produce 2-complex
$X^{\prime}$ violating (c).

This shows that any minimal cycle $Z\subset X$ is homeomorphic to
$Z_{4}=P^{2}\cup\Delta^{2}$.

The union of the edges of degree 3 in $Z$ is a closed curve and cutting along
this curve disconnects $Z$ onto a copy of $P^{2}$ and $\Delta^{2}$. Thus, we
may think of $P^{2}$ as being a subcomplex of $Z$. If $P^{2}\not\subset S$
then there is a 2-simplex $\sigma\subset P^{2}-S$. Then the curve
$\partial\sigma\subset Z-\sigma\subset X-\sigma$ is null-homotopic and hence
the inclusion $X^{\prime}=Z-\sigma\to X$ induces an isomorphism
$\pi_{1}(X^{\prime})\to\pi_{1}(X)$ contradicting (c). This argument shows that
$P^{2}\subset S$ and hence $P^{2}=S$. Since $\pi_{1}(S)\to\pi_{1}(Z)$ is
trivial, it follows from the minimality of $X$ (property (c)) that $Z=X$.

Since $\mu(X)>1/2$, by formula (2) we obtain that $2\chi(X)+L(X)>0$ or
equivalently $L(X)\geq-3$ (as $\chi(X)=2$ since $X$ is homotopy equivalent to
the 2-sphere). On the other hand, $L(X)\leq-3$ since $X$ is closed and has at
least 3 edge of degree 3. Thus $L(X)=-3$.

Using formula (11) we find that

$\mu(X,S)=\frac{1}{2}-\frac{1}{2(f(X)-10)}<\frac{1}{2}$

and then applying Theorem 4.3 we find that for

$n^{-3/5}\ll p\ll n^{-1/2-\epsilon},$

with probability tending to 1, there exist embedding $S\to Y$ (where $Y\in
Y(n,p)$ is random) which cannot be extended to an embedding of $X\to Y$ for
any $X\in{\mathcal{S}}_{\epsilon}$.

Let $Y^{\prime}_{n}\subset Y(n,p)$ denote the set of complexes $Y\in Y(n,p)$
such that there exists an simplicial embedding $S\to Y$ which cannot be
extended to an embedding $X\to Y$, for any $X\in{\mathcal{S}}_{\epsilon}$. We
have shown earlier that ${\mathbb{P}}(Y_{n}^{\prime})\to 1$ as $n\to\infty$.

Consider the finite family $\mathcal{F}$ of isomorphism types of simplicial
complexes $T$ having at most $10+3c_{\epsilon}^{-1}$ faces and satisfying
$\tilde{\mu}(T)\leq 1/2+\epsilon$. By Lemma 1.1, since we assume that $p\ll
n^{-1/2-\epsilon}$, the set $Y^{\prime\prime}_{n}\subset Y(n,p)$ of
2-complexes $Y\in Y(n,p)$ having the property that none of the complexes
$T\in{\mathcal{F}}$ is embeddable into $Y$, satisfies
${\mathbb{P}}(Y^{\prime\prime}_{n})\to 1$, as $n\to\infty$.

Besides, let $Y^{\prime\prime\prime}_{n}\subset Y(n,p)$ denote the set of
complexes satisfying Theorem 3.4. We know that
${\mathbb{P}}(Y^{\prime\prime\prime}_{n})\to 1$ as $n\to\infty$.

Now, let $Y\in Y_{n}^{\prime}\cap Y_{n}^{\prime\prime}\cap
Y^{\prime\prime\prime}_{n}$ and let $S\subset Y$ be an embedding which cannot
be extended to an embedding $X\to Y$ for $X\in{\mathcal{S}}_{\epsilon}$. Let
us show that $S\subset Y$ is essential. Assuming the contrary, if the
embedding $S\subset Y$ is not essential then the central circle $\gamma$ of
$S$ (of length 3) extends to a simplicial map of a simplicial disc into $Y$.
Under the assumption $p\ll n^{-1/2-\epsilon}$, using Theorem 3.4, we find that
the circle $\gamma$ extends to a simplicial map $b:\Delta^{2}\to Y$,
$b|\partial\Delta^{2}=\gamma$, into $Y$ of a simplicial disc of area $\leq
3c_{\epsilon}^{-1}$ where $c_{\epsilon}>0$ depends only on the value of
$\epsilon$. Since $S\cup b(\Delta^{2})$ is embedded into $Y$ we obtain that
$\tilde{\mu}(S\cup b(\Delta^{2}))>1/2+\epsilon$. Hence, if $S\subset Y$ is not
essential then there would exist a complex $X\in{\mathcal{S}}_{\epsilon}$,
where $S\subset X\subset S\cup b(\Delta^{2})$, such that the embedding
$S\subset Y$ extends to an embedding $X\subset Y$. This gives a contradiction.
∎

###  4.3 Absence of higher torsion

In this subsection we prove the following statement complementing Theorem 4.5.

######  Theorem 4.6.

Assume that the probability parameter $p$ satisfies

$\displaystyle p\ll n^{-1/2-\epsilon},$ (15)

where $\epsilon>0.$ Let $m\geq 3$ be a prime number. Then a random 2-complex
$Y\in Y(n,p)$, with probability tending to 1, has the following property: for
any subcomplex $Y^{\prime}\subset Y$ the fundamental group
$\pi_{1}(Y^{\prime})$ has no elements of order $m$.

Let $\Sigma$ be a simplicial 2-complex homeomorphic to the Moore surface

$M({\mathbf{Z}}_{m},1)=S^{1}\cup_{f_{m}}e^{2},\quad\mbox{where}\quad\quad
m\geq 3;$

it is obtained from the circle $S^{1}$ by attaching a 2-cell via the degree
$m$ map $f_{m}:S^{1}\to S^{1}$, $f_{m}(z)=z^{m}$, $z\in S^{1}$. The 2-complex
$\Sigma$ has a well defined circle $C\subset\Sigma$ (which we shall call the
singular circle) which is the union of all edges of degree $m$; all other
edges of $\Sigma$ have degree $2$. Clearly, the homotopy class of the singular
circle generates the fundamental group
$\pi_{1}(\Sigma)\simeq{\mathbf{Z}}_{m}$.

Next we define an integer $N_{m}(Y)\geq 0$ associated to any connected
2-complex $Y$. If $\pi_{1}(Y)$ has no $m$-torsion we set $N_{m}(Y)=0.$ If
$\pi_{1}(Y)$ has elements of order $m$ we shall consider homotopically
nontrivial simplicial maps $\gamma:C_{r}\to Y$, where $C_{r}$ is the
simplicial circle with $r$ edges, such that

  1. (a)

$\gamma^{m}$ is null-homotopic (as a free loop in $Y$);

  2. (b)

$r$ is minimal: for $r^{\prime}<r$ any simplicial loop
$\gamma:C_{r^{\prime}}\to Y$ satisfying (a) is homotopically trivial.

Any such simplicial map $\gamma:C_{r}\to Y$ can be extended to a simplicial
map $f:\Sigma\to Y$ of a triangulation $\Sigma$ of the Moore surface, such
that the singular circle $C$ of $\Sigma$ is isomorphic to $C_{r}$ and
$f|C=\gamma$. We shall say that a simplicial map $f:\Sigma\to Y$ is
$m$-minimal if it satisfies (a), (b) and the number of 2-simplexes in $\Sigma$
is the smallest possible. Now, we denote by

$N_{m}(Y)\in{\mathbf{Z}}$

the number of 2-simplexes in a triangulation of the Moore surface $\Sigma$
admitting an $m$-minimal map $f:\Sigma\to Y$.

######  Lemma 4.7.

Let $Y$ be a 2-complex satisfying $I(Y)\geq c>0$ (where the quantity $I(Y)$ is
defined in §3). Let $m\geq 3$ be an odd prime. Then one has

$N_{m}(Y)\leq\left(\frac{6m}{c}\right)^{2}.$

###### Proof.

We shall assume that the fundamental group of $Y$ contains an element of order
$m$; otherwise $N_{m}(Y)=0$. Consider an $m$-minimal simplicial map
$f:\Sigma\to Y$,

$\displaystyle A(\Sigma)=N_{m}(Y),$ (16)

where $A(\Sigma)$ denotes the number of 2-simplexes in $\Sigma$. It is obvious
from the $m$-minimality of $f$ that the singular circle $C\subset\Sigma$ is
the shortest (in terms of the number of edges) homotopically nontrivial
simplicial loop in $\Sigma$, i.e.

$\displaystyle|C|={\rm{sys}}(\Sigma).$ (17)

Consider the loop $\gamma=f|C$, $|\gamma|=|C|={\rm{sys}}(\Sigma)$. We know
that $\gamma^{m}$ is homotopically trivial in $Y$ and the inequality $I(Y)\geq
c>0$ implies that $\gamma^{m}$ bounds in $Y$ a disc of area at most
$m\cdot|\gamma|\cdot c^{-1}$. The 2-complex $\Sigma$ is obtained from a
simplicial disc $D$ by dividing its boundary into $m$ intervals of equal
length and identifying them to each other. If $A(D)>m\cdot|\gamma|\cdot
c^{-1}$ then one could replace the disc $D$ by the minimal spanning disc for
$\gamma^{m}$ obtaining a simplicial map $\Sigma^{\prime}\to Y$ which has
smaller area contradicting the $m$-minimality. Thus, we obtain

$\displaystyle A(\Sigma)\leq c^{-1}\cdot m\cdot{\rm{sys}}(\Sigma).$ (18)

Inequality (7) gives

$\displaystyle{\rm{sys}}(\Sigma)\leq 6\cdot A(\Sigma)^{1/2}.$ (19)

Combining (16), (18) and (19) we obtain

$N_{m}(Y)\,=\,A(\Sigma)\leq\left(\frac{6m}{c}\right)^{2}.$

∎

######  Theorem 4.8.

Assume that the probability parameter $p$ satisfies $p\ll n^{-1/2-\epsilon}$
where $\epsilon>0$ is fixed. Let $m\geq 3$ be an odd prime. Then there exists
a constant $C_{\epsilon}>0$ such that a random 2-complex $Y\in Y(n,p)$ with
probability tending to 1 has the following property: for any subcomplex
$Y^{\prime}\subset Y$ one has

$\displaystyle N_{m}(Y^{\prime})\leq C_{\epsilon}.$ (20)

###### Proof.

We know from Theorem 3.4 that, with probability tending to 1, a random
2-complex $Y$ has the following property: for any subcomplex
$Y^{\prime}\subset Y$ one has $I(Y^{\prime})\geq c_{\epsilon}>0$ where
$c_{\epsilon}>0$ is the constant given by Theorem 3.4. Then, setting
$C=\left(\frac{6m}{c_{\epsilon}}\right)^{2}$, the inequality (20) follows from
Lemma 4.7. ∎

###### Proof of Theorem 4.6.

Let $c_{\epsilon}>0$ be the number given by Theorem 3.4. Consider the finite
set of all isomorphism types of triangulations $\mathcal{S}_{m}=\\{\Sigma\\}$
of the Moore surface $M({\mathbf{Z}}_{m},1)$ having at most
$\left(\frac{6m}{c_{\epsilon}}\right)^{2}$ two-dimensional simplexes. Let
$\mathcal{X}_{m}$ denote the set of isomorphism types of images of all
surjective simplicial maps $\Sigma\to X$ inducing injective homomorphisms
$\pi_{1}(\Sigma)={\mathbf{Z}}_{m}\to\pi_{1}(X)$, where
$\Sigma\in\mathcal{S}_{m}$. The set $\mathcal{X}_{m}$ is also finite.

From Theorem 4.8 we obtain that, with probability tending to one, for any
subcomplex $Y^{\prime}\subset Y$, either $\pi_{1}(Y^{\prime})$ has no
$m$-torsion, or there exists an $m$-minimal map $f:\Sigma\to Y^{\prime}$ with
$\Sigma$ having at most $\left(\frac{6m}{c_{\epsilon}}\right)$ simplexes of
dimension 2; in the second case the image $X=f(\Sigma)$ is a subcomplex of
$Y^{\prime}$ and $f:\Sigma\to X$ induces a monomorphism
$\pi_{1}(\Sigma)\to\pi_{1}(X)$, i.e. $X\in{\mathcal{X}}_{m}$.

From Corollary 2.10 we know that the fundamental group of any 2-complex
satisfying $\tilde{\mu}(X)>1/2$ is a free product of several copies of
${\mathbf{Z}}$ and ${\mathbf{Z}}_{2}$ and has no $m$-torsion, as we assume
that $m\geq 3$. Since the fundamental group of any $X\in\mathcal{X}_{m}$ has
$m$-torsion, where $m\geq 3$, one has $\tilde{\mu}(X)\leq 1/2$ for any
$X\in\mathcal{X}_{m}$. Hence, using the finiteness of $\mathcal{X}_{m}$ and
the results on the containment problem (see [5], Theorem 15) we see that for
$p\ll n^{-1/2-\epsilon}$ the probability that a random complex $Y\in Y(n,p)$
contains a subcomplex isomorphic to one of the complexes $X\in\mathcal{X}_{m}$
tends to $0$ as $n\to\infty$. Hence, we obtain that (a.a.s.) any subcomplex
$Y^{\prime}\subset Y$ does not contain $X\in\mathcal{X}_{m}$ as a subcomplex
and therefore the fundamental group of $Y^{\prime}$ has no $m$-torsion. ∎

##  5 Minimal spheres and the Whitehead Conjecture

######  Definition 5.1.

Let $Y$ be a simplicial complex with $\pi_{2}(Y)\not=0$. We define a numerical
invariant $M(Y)\in{\mathbf{Z}}$, $M(Y)\geq 4$, as the minimal number of faces
in a 2-complex $\Sigma$ homeomorphic to the sphere $S^{2}$ such that there
exists a homotopically nontrivial simplicial map $\Sigma\to Y$. We define
$M(Y)=0$, if $\pi_{2}(Y)=0$.

Our first goal in this section is to prove the following theorem:

######  Theorem 5.2.

Assume that the probability parameter $p$ satisfies $p\ll n^{-1/2-\epsilon}$
where $\epsilon>0$ is fixed. Then there exists a constant $C=C_{\epsilon}$
such that a random 2-complex $Y\in Y(n,p)$ with probability tending to 1 has
the following property: for any subcomplex $Y^{\prime}\subset Y$ one has

$\displaystyle M(Y^{\prime})\leq C.$ (21)

In other words, in the specified range of $p$, the numbers $M(Y^{\prime})$
have a uniform upper bound, a.a.s.

In the proof of Theorem 5.2 we will use the following version of the notion of
Cheeger’s constant. For a pure simplicial 2-complex $\Sigma$ one defines the
Cheeger’s constant $h(\Sigma)$ as

$\displaystyle h(\Sigma)=\min_{S\subset\Sigma}\left\\{\frac{|\partial
S|}{A(S)};A(S)\leq A(\Sigma)/2\right\\},$ (22)

where $S\subset\Sigma$ runs over all pure subcomplexes. Here $|\partial S|$
denotes the length of the boundary (the number of edges) and $A(S)$ and
$A(\Sigma)$ denote the area of $S$ and $\Sigma$, i.e. the number of
2-simplexes.

Note that in (22) one may always assume that $S\subset\Sigma$ is strongly
connected. Indeed, if $S=\cup_{j}S_{j}$ are the strongly connected components
of $S$ then $|\partial S|=\sum_{j}|\partial S_{j}|$ and
$A(S)=\sum_{j}A(S_{j})$ and therefore,

$\frac{|\partial S|}{A(S)}\geq\min_{j}\frac{|\partial S_{j}|}{A(S_{j})}.$

In the case when $\Sigma$ is homeomorphic to the sphere $S^{2}$ one can
require the subcomplex $S\subset\Sigma$ which appears in the formula (22) to
be homeomorphic to a disc. Indeed, if $S\subset\Sigma$ is strongly connected
and $\frac{|\partial S|}{A(S)}=h(S)$, $A(S)\leq A(\Sigma)/2$, consider the
strongly connected components of the closure of the complement
$\overline{\Sigma-S}=\cup_{j}D_{j}$. Each $D_{j}$ is a disc and $|\partial
S|=\sum_{j}|\partial D_{j}|$ and $A(S)\leq A(\Sigma-S)=\sum_{j}A(D_{j})$.
Hence

$h(\Sigma)=\frac{|\partial S|}{A(S)}\geq\frac{\sum_{j}|\partial
D_{j}|}{\sum_{j}A(D_{j})}\geq\min_{j}\frac{|\partial D_{j}|}{A(D_{j})}$

and in particular for some $j_{0}$ one has $\frac{|\partial
D_{j_{0}}|}{A(D_{j_{0}})}\leq h(\Sigma)$. From now on we may assume that
$A(D_{j_{0}})>A(\Sigma)/2$ since otherwise the proof is complete. Consider the
disc $C=\overline{\Sigma-D_{j_{0}}}$. Then $A(C)\leq A(\Sigma)/2$ and

$A(C)\geq A(S),\quad|\partial C|\leq|\partial S|$

and we obtain

$h(\Sigma)=\frac{|\partial S|}{A(S)}\geq\frac{|\partial C|}{A(C)}.$

Thus the value $h(\Sigma)$ in (22) is achived on subdiscs.

Our next two results are deterministic. We show that the isoperimetric
constant can be used to estimate above the value $M(Y)$.

######  Lemma 5.3.

Let $Y$ be a 2-complex with $I(Y)\geq c>0$. Let $f:\Sigma\to Y$ be a
homotopically nontrivial simplicial map where $\Sigma$ is homeomorphic to
$S^{2}$ and $A(\Sigma)=M(Y)$. Then $h(\Sigma)\geq c$.

###### Proof.

Assume that $h(\Sigma)<c$. Then (due to our discussion above) there exists a
simplicial subdisc $S\subset\Sigma$ with $A(S)\leq A(\Sigma)/2$ and
$\frac{|\partial S|}{A(S)}<c$. The curve $\gamma=f|\partial S$ is a null-
homotopic loop in $Y$ and $f|S:S\to Y$ is a bounding disk for $\gamma$. We
claim that this disc has the smallest area among all bounding discs for
$\gamma$ in $Y$. Indeed, if there existed a spanning disc $b:D\to Y$,
$b|\partial D=\gamma$, with $A(D)<A(S)$ then we may define two maps of the
sphere $S^{2}\to Y$, both having smaller area than $f$. These maps are
$\phi:S\cup D\to Y$ and $\phi^{\prime}:S^{\prime}\cup D\to Y$ where
$S^{\prime}=\overline{\Sigma-S}$. Here $\phi|S=f|S$,
$\phi|D=b=\phi^{\prime}|D$, $\phi^{\prime}|S^{\prime}=f|S^{\prime}$. Clearly
at least one of $\phi$ and $\phi^{\prime}$ is not null-homotopic, since if
both $\phi$ and $\phi^{\prime}$ were null-homotopic then the original map
$S^{2}\to Y$ was null-homotopic as well. Thus we obtain $A(S)=A_{Y}(\gamma)$
and $\frac{|\gamma|}{A_{Y}(\gamma)}<c$ contradicting our assumption $I(Y)\geq
c$. ∎

######  Corollary 5.4.

Let $Y$ be a 2-complex with $I(Y)\geq c>0$. Then

$\displaystyle M(Y)\leq\left(\frac{16}{c}\right)^{2}.$ (23)

###### Proof.

Papasoglu [15] proved the inequality

$h(\Sigma)\leq\frac{16}{\sqrt{A(\Sigma)}}$

valid for any simplicial sphere. By Lemma 5.3, one has $h(\Sigma)>c$ for the
homotopically nontrivial map $\Sigma\to Y$ with the minimal $A(\Sigma)$. This
implies that $A(\Sigma)\leq 16^{2}/c^{2}$ which is equivalent to our
statement. ∎

###### Proof of Theorem 5.2.

By Theorem 3.4 one has $I(Y^{\prime})>c_{\epsilon}$, a.a.s. where
$c_{\epsilon}>0$ depends only on $\epsilon$. Thus, in view of Corollary 5.4,
the inequality (21) is satisfied with $C=256/c^{2}_{\epsilon}$. ∎

Next we characterise aspherical subcomplexes of random 2-complexes:

######  Theorem 5.5.

Assume that $p\ll n^{-1/2-\epsilon}$ for a fixed $\epsilon>0$. Then a random
2-complex $Y\in Y(n,p)$ has the following property with probability tending to
one as $n\to\infty$: for any subcomplex $Y^{\prime}\subset Y$ the following
properties are equivalent:

(A)

$Y^{\prime}$ is aspherical;

(B)

$Y^{\prime}$ contains no subcomplexes $S\subset Y^{\prime}$ with at most
$2\epsilon^{-1}$ faces which are homeomorphic to the sphere $S^{2}$, the
projective plane ${\mathbf{RP}}^{2}$ or the complexes $Z_{2},Z_{3}$ shown in
Figure 3.

In particular, a random 2-complex $Y\in Y(n,p)$ has the following property
with probability tending to one as $n\to\infty$: any subcomplex
$Y^{\prime}\subset Y$ with $b_{2}(Y^{\prime})=0$ is aspherical if and only if

(B’)

$Y^{\prime}$ contains no subcomplexes $S\subset Y^{\prime}$ with at most
$2\cdot\epsilon^{-1}$ faces which are homeomorphic to the projective plane
${\mathbf{RP}}^{2}$.

###### Proof.

We first show that (A) $\Rightarrow$ (B). It is obvious that an aspherical
2-complex cannot contain as a subcomplex none of $S^{2}$ or $Z_{2}$, $Z_{3}$;
otherwise there would be a nontrivial spherical homology class. By a theorem
of W.H. Cockcroft [4], an aspherical 2-complex cannot contain a projective
plane.

Next we show that (B) $\Rightarrow$ (A) a.a.s. Let $Y^{\prime}\subset Y$ be a
subcomplex where $Y\in Y(n,p)$ is random. Assume that $Y^{\prime}$ contains no
subcomplexes with at most $2/\epsilon$ faces which are homeomorphic to either
$S^{2}$, ${\mathbf{RP}}^{2}$ or $Z_{2},Z_{3}$, see above. If $Y^{\prime}$ is
not aspherical then by Theorem 5.2, $M(Y^{\prime})\leq C$ where $C$ depends
only on $\epsilon$. There exist finitely many isomorphism types
$\\{S_{j}\\}_{j\in J}$ of triangulations of $S^{2}$ with at most $C$ faces. By
Lemma 1.1 the probability that a random 2-complex $Y$ contains an image
$\phi_{j}(S_{j})$ satisfying $\tilde{\mu}(\phi_{j}(S_{j}))<1/2+\epsilon$ tends
to zero as $n\to\infty$. Thus we only have to consider the images of
homotopically nontrivial simplicial maps $\phi_{j}:S_{j}\to Y^{\prime}$
satisfying $\tilde{\mu}(\phi_{j}(S_{j}))\geq 1/2+\epsilon$.

If the second Betti number of the image is nonzero,
$b_{2}(\phi_{j}(S_{j}))\not=0$, then the image $\phi_{j}(S_{j})$ contains a
minimal cycle $Z$ satisfying $\tilde{\mu}(Z)\geq 1/2+\epsilon$. By Theorem
2.5, such $Z$ must be homeomorphic to one of the complexes
$Z_{1},Z_{2},Z_{3},Z_{4}$. For $i=1,2,3$ one has

$\epsilon\,\leq\,\tilde{\mu}(Z_{i})-\frac{1}{2}\,\leq\,\frac{2}{f(Z_{i})}$

and hence $f(Z_{i})\leq 2/\epsilon$. For $i=4$, we have
$Z_{4}=P^{2}\cup\Delta^{2}$ and

$\mu(P^{2})=\frac{1}{2}+\frac{1}{f(P^{2})}\geq\tilde{\mu}(Z_{4})\geq\frac{1}{2}+\epsilon$

implying that $f(P^{2})\leq 2\epsilon^{-1}$. Now we may use our assumptions
concerning $Y^{\prime}$, implying that $Y^{\prime}$ contains no subcomplexes
homeomorphic to $Z_{1},\dots,Z_{4}$ leading to contradiction.

Consider now the remaining case $b_{2}(\phi_{j}(S_{j}))=0$. By Lemma 1.1 one
has

$\mu(\phi_{j}(S_{j}))\geq\tilde{\mu}(\phi_{j}(S_{j}))\geq\frac{1}{2}+\epsilon.$

Now, applying Lemma 2.9, we see that the image $\phi_{j}(S_{j})$ is an
iterated wedge of projective planes. The argument similar to the one used in
the previous paragraph shows that each of these projective planes $P^{2}$ has
at most $2\epsilon^{-1}$ faces. Hence we obtain a contradiction to our
assumption.

∎

The following results are corollaries of Theorem 5.5:

######  Corollary 5.6.

Assume that $p\ll n^{-1/2-\epsilon}$ where $\epsilon>0$ is fixed. Then a
random 2-complex $Y\in Y(n,p)$ has the following property with probability
tending to one as $n\to\infty$: any aspherical subcomplex $Y^{\prime}\subset
Y$ satisfies the Whitehead conjecture, i.e. if a subcomplex $Y^{\prime}\subset
Y$ is aspherical then all subcomplexes of $Y^{\prime}$ are also aspherical.

###### Proof.

Let $Y^{\prime}\subset Y$ be aspherical. Then by the previous Theorem,
$Y^{\prime}$ has property (B). Hence any subcomplex $Y^{\prime\prime}\subset
Y^{\prime}$ has property (B). Applying Theorem 5.5 again we obtain that
$Y^{\prime\prime}$ is aspherical. This completes the proof. ∎

######  Corollary 5.7.

Assume that $p\ll n^{-1/2-\epsilon}$ where $\epsilon>0$ is fixed. Then a
random 2-complex $Y\in Y(n,p)$ has the following property with probability
tending to one as $n\to\infty$: a subcomplex $Y^{\prime}\subset Y$ is
aspherical if and only if any subcomplex $S\subset Y^{\prime}$ with at most
$2\epsilon^{-1}$ faces is aspherical.

###### Proof.

Indeed, in one direction the result follows from Corollary 5.6. In the other
direction the result follows from the implication (B) $\Rightarrow$ (A) of
Theorem 5.5. ∎

######  Corollary 5.8.

Assume that $p\ll n^{-1/2-\epsilon}$ where $\epsilon>0$ is fixed. Then a
random 2-complex $Y\in Y(n,p)$ has the following property with probability
tending to one as $n\to\infty$: any subcomplex $Y^{\prime}\subset Y$ with
$H_{2}(Y^{\prime};{\mathbf{Z}}_{2})=0$ is aspherical.

###### Proof.

If $H_{2}(Y^{\prime};{\mathbf{Z}}_{2})=0$ then $Y^{\prime}$ cannot have
subcomplexes homeomorphic to $S^{2}$, ${\mathbf{RP}}^{2}$, $Z_{2}$ and
$Z_{3}$. Therefore $Y^{\prime}$ is aspherical by Theorem 5.5. ∎

######  Corollary 5.9.

Assume that $p\ll n^{-3/5}$. Then for a random 2-complex $Y\in Y(n,p)$ the
fundamental group $\pi_{1}(Y)$ has cohomological dimension at most 2, a.a.s.
In particular, under this assumption on $p$ the fundamental group $\pi_{1}(Y)$
has no torsion, a.a.s. Moreover, for $p\ll n^{-3/5}$, any subcomplex
$Y^{\prime}\subset Y$ with $b_{2}(Y^{\prime})=0$ is aspherical a.a.s.

###### Proof.

We shall apply Theorem 5.5 with $\epsilon=1/10$, so that $1/2+\epsilon=3/5$
and $2\epsilon^{-1}=20$. Thus we shall consider embeddings of triangulated
$S^{2}$, $Z_{2}$, $Z_{3}$ and ${\mathbf{RP}}^{2}$ into $Y\in Y(n,p)$ having at
most $20$ faces.

For any triangulation of ${\mathbf{RP}}^{2}$ one has
$\tilde{\mu}({\mathbf{RP}}^{2})\leq 3/5$ (see [5], Corollary 22) and by Lemma
1.1, no projective plane with at most 20 faces is contained in $Y\in Y(n,p)$
under the assumption $p\ll n^{-3/5}$.

Thus $Y$ may only contain copies of $S^{2},Z_{2},Z_{3}$ with at most 20 faces.
We produce now a sequence of subcomplexes $Y=Y_{0}\supset Y_{1}\supset
Y_{2}\supset\dots\supset Y_{k}$ with $k\leq b_{2}(Y)$ as follows. Each
$Y_{i+1}$ is obtained from $Y_{i}$ by removing a face belonging to a
subcomplex homeomorphic to $S^{2},Z_{2}$ or $Z_{3}$. Then clearly
$\pi_{1}(Y_{i+1})=\pi_{1}(Y_{i})$ and the last subcomplex $Y_{k}\subset Y$ is
aspherical by Theorem 5.5.

Therefore, we obtain that there exists a 2-dimensional complex $Y_{k}$ having
fundamental group $\pi_{1}(Y_{k})=\pi_{1}(Y)$. This implies that the
cohomological dimension of $\pi_{1}(Y)$ is at most $2$.

As for the second statement of the Corollary, we observe that any subcomplex
$Y^{\prime}\subset Y$ with $b_{2}(Y^{\prime})=0$ cannot contain
$S^{2},Z_{2},Z_{3}$. It also cannot contain copies of the real projective
plane, as explained above. Thus, by Theorem 5.5, $Y^{\prime}$ must be
aspherical, a.a.s. ∎

######  Remark 5.10.

The method of the proof of Corollary 5.9 gives in fact a stronger result: for
$p\ll n^{-3/5}$ a random 2-complex $Y\in Y(n,p)$ has the following property
with probability tending to one: the fundamental group of any subcomplex
$Y^{\prime}\subset Y$ has cohomological dimension at most $2$, i.e.
${cd}(\pi_{1}(Y^{\prime}))\leq 2$.

Using Theorem 5.5 one may generate random aspherical 2-complexes as follows.
Start with a random 2-complex $Y\in Y(n,p)$ where $p\ll n^{-1/2-\epsilon}$.
Let $\mathcal{A}_{\epsilon}=\\{Z\\}$ be the set of all isomorphism types of
minimal cycles having at most $2\epsilon^{-1}$ faces with the property
$\mu(Z)>1/2$. The set $\mathcal{A}_{\epsilon}$ is finite; each
$Z\in\mathcal{A}_{\epsilon}$ is homeomorphic to one of the 2-complexes
$Z_{1},Z_{2},Z_{3},Z_{4}$ described in Theorem 2.5. Now one finds all
subcomplexes of the random complex $Y$ which are isomorphic to the complexes
$Z\in\mathcal{A}_{\epsilon}$ and removes randomly (or by applying certain
rule) one of its faces satisfying the conditions of Corollary 2.6. The
obtained complex $Y^{\prime}\subset Y$ is aspherical, a.a.s., by Theorem 5.5;
clearly $\pi_{1}(Y^{\prime})=\pi_{1}(Y)$.

In the next statement we show that the aspherical 2-complex $Y^{\prime}$ has
large second Betti number and hence the fundamental group
$\pi_{1}(Y^{\prime})=\pi_{1}(Y)$ has cohomological dimension 2. Combined with
Corollary 5.9, Proposition 5.11 implies Theorem A from the Introduction.

######  Proposition 5.11.

Assume that for some $c>3$ and $\epsilon>0$ one has

$\displaystyle\frac{c}{n}\,<\,p\,<\,n^{-1/2-\epsilon}.$ (24)

Then the second Betti number of the random aspherical 2-complex $Y^{\prime}$
described in the preceding paragraph satisfies

$\displaystyle
n^{2}\cdot\frac{c-3}{8}\,\leq\,b_{2}(Y^{\prime})\,\leq\,n^{5/2-\epsilon},$
(25)

a.a.s.

This result is similar to Theorem 3 from [6] and its proof uses the same
sequence of arguments.

###### Proof.

Let $f_{2},b_{2}:Y(n,p)\to{\mathbf{Z}}$ denote the number of 2-simplexes in a
random complex and the second Betti number, viewed as random variables. Note
that $f_{2}$ is binomially distributed with expectation $p\binom{n}{3}$. We
have $f_{2}-\binom{n-1}{2}\,\leq\,b_{2}\,\leq\,f_{2}.$ The inequality (2.6) on
page 26 of [10] with $t=n^{7/4}$ gives

${\mathbb{P}}(f_{2}\leq
p\binom{n}{3}-t)\leq\exp\left(-\frac{t^{2}}{2p\binom{n}{3}}\right)\leq\exp\left(-\sqrt{n}\right).$

We see that with probability at least $1-\exp\left(-\sqrt{n}\right)$, one has

$b_{2}\geq f_{2}-\binom{n-1}{2}\geq
p{\binom{n}{3}}-{\binom{n-1}{2}}-t\geq\binom{n-1}{2}\cdot\left(\frac{c-3}{3}\right)-t\geq
n^{2}\cdot\frac{c-3}{7}$

for large $n$; here $b_{2}=b_{2}(Y)$.

For any $Z\in{\mathcal{A}}_{\epsilon}$ consider the random variable
$k_{Z}:Y(n,p)\to{\mathbf{Z}}$, where for $Y\in Y(n,p)$ the value $k_{Z}(Y)$ is
the number of subcomplexes of $Y$ which are isomorphic (as simplicial
complexes) to $Z$. The expectation of $k_{Z}$ satisfies $\mathbb{E}(k_{Z})\leq
n^{v(Z)}p^{f_{2}(Z)}$. For any $Z\in{\mathcal{A}}_{\epsilon}$ one has
$L(Z)\leq 0$ and $\chi(Z)\leq 2$ implying

$\mu(Z)=\frac{v(Z)}{f_{2}(Z)}\leq\frac{1}{2}+\frac{2}{f_{2}(Z)},$

as follows from formula (2). Hence we have

$v(Z)\leq f_{2}(Z)/2+2$

and therefore

$\displaystyle\mathbb{E}(k_{Z})$ $\displaystyle\leq$ $\displaystyle
n^{v(Z)}p^{f_{2}(Z)}$ $\displaystyle\leq$ $\displaystyle
n^{f_{2}(Z)/2+2}p^{f_{2}(Z)}$ $\displaystyle\leq$ $\displaystyle
n^{f_{2}(Z)/2+2}n^{{(-1/2-\epsilon)}f_{2}(Z)}$ $\displaystyle=$ $\displaystyle
n^{2-\epsilon f_{2}(Z)}\leq n^{2-4\epsilon}.$

Let $k=\sum_{Z\in{\mathcal{A}}_{\epsilon}}k_{Z}$ be the sum random variable.
Then we obtain

$\mathbb{E}(k)=\sum_{Z}\mathbb{E}(k_{Z})\leq|{\mathcal{A}}_{\epsilon}|\cdot
n^{2-4\epsilon}.$

The Markov inequality ${\mathbb{P}}(k\geq t)\leq\frac{\mathbb{E}(k)}{t}$ with
$t=n^{2-3\epsilon}$ gives ${\mathbb{P}}(k\geq
n^{2-3\epsilon})\leq|{\mathcal{A}}_{\epsilon}|\cdot n^{-\epsilon}.$ Thus, with
probability tending to one as $n\to\infty$, one has

$b_{2}(Y^{\prime})\geq b_{2}(Y)-k(Y)\geq
n^{2}\cdot\frac{c-3}{7}-n^{2-3\epsilon}\geq n^{2}\cdot\frac{c-3}{8}>0$

for $n\to\infty$. This proves the left inequality in (25).

From inequality (2.5) on page 26 of [10] with $t=n^{7/4}$ one obtains that
with probability at least $1-\exp(-\sqrt{n})$ one has
$f_{2}\,\leq\,p\binom{n}{3}+t$ and hence $b_{2}(Y^{\prime})\leq b_{2}(Y)\leq
f_{2}\leq p\binom{n}{3}+t\leq n^{5/2-\epsilon}.$ This proves the right
inequality in (25). ∎

As above, for a positive integer $m$, let $M_{m}$ denote the Moore surface,
i.e. the quotient space of the disc $D^{2}\subset{\mathbf{C}}$ (the unit disc
on the complex plane) where every point $z\in\partial D^{2}$ is identified
with $z^{m}$.

######  Corollary 5.12.

If $p\ll n^{-1/2-\epsilon}$ then a random 2-complex $Y\in Y(n,p)$ with
probability tending to one as $n\to\infty$ has the following property: no
subcomplex $Y^{\prime}\subset Y$ homeomorphic to a Moore surface $M_{m}$ with
$m\geq 3$.

###### Proof.

This is a corollary of Theorem 5.5 since for $m\geq 3$ the Moore surface
$M_{m}$ (a) contains no subcomplexes homeomorphic to the sphere, to the real
projective space and to complexes $Z_{2},Z_{3}$ (shown in Figure 3) and (b)
the Moore surface $M_{m}$ is not aspherical. ∎

A similar argument provides an alternative proof of Corollary 3.7.

##  6 Appendix: Proof of Theorem 3.4

The proof of Theorem 3.4 given below is similar to the arguments of [2] and is
based on two auxiliary results: (1) the local-to-global principle of Gromov
[9] and on (2) Theorem 6.2 giving uniform isoperimetric constants for
complexes satisfying $\tilde{\mu}(X)\geq 1/2+\epsilon$.

The local-to-global principle of Gromov can be stated as follows:

######  Theorem 6.1.

Let $X$ be a finite 2-complex and let $C>0$ be a constant such that any pure
subcomplex $S\subset X$ having at most $(44)^{3}\cdot C^{-2}$ two-dimensional
simplexes satisfies $I(S)\geq C$. Then $I(X)\geq C\cdot 44^{-1}$.

Theorem 6.1 follows from Theorem 3.9 from [2]. Indeed, suppose that the
assumptions of Theorem 6.1 are satisfied. Let $\gamma:S^{1}\to X$ be a
simplicial loop with $A_{X}(\gamma)<(44)^{3}\cdot C^{-2}=44\rho^{2}$ where
$\rho=44/C$. Then there is a pure subcomplex $S\subset X$ with at most
$(44)^{3}\cdot C^{-2}$ faces, which contains $\gamma$ and the minimal spanning
disc for $\gamma$ in $X$, such that

$\frac{|\gamma|}{A_{S}(\gamma)}\geq I(S)\geq C=44/\rho,$

by our assumption, i.e.

$A_{X}(\gamma)=A_{S}(\gamma)\leq\frac{\rho}{44}\cdot|\gamma|.$

Applying Theorem 3.9 from [2] we obtain $I(X)\geq\rho^{-1}=C/44$.

Let $X$ be a 2-complex satisfying $\tilde{\mu}(X)>1/2$. Then by Corollary 2.10
the fundamental group of $X$ is hyperbolic as it is a free product of several
copies of cyclic groups ${\mathbf{Z}}$ and ${\mathbf{Z}}_{2}$. Hence,
$I(X)>0$. The following theorem gives a uniform lower bound for the numbers
$I(X)$.

######  Theorem 6.2.

Given $\epsilon>0$ there exists a constant $C_{\epsilon}>0$ such that for any
finite pure 2-complex $X$ with $\tilde{\mu}(X)\geq 1/2+\epsilon$ one has
$I(X)\geq C_{\epsilon}$.

This statement is equivalent to Lemma 3.5 from [2] and plays a crucial role in
the proof of Theorem 3.4. A proof of Theorem 6.2 (which uses the method of [2]
but is presented in a slightly different form) is given below in §6.1.

###### Proof of Theorem 3.4 using Theorem 6.1 and Theorem 6.2.

Let $C_{\epsilon}$ be the constant given by Theorem 6.2. Consider the set
$\mathcal{S}$ of isomorphism types of all pure 2-complexes having at most
$44^{3}\cdot C_{\epsilon}^{-2}$ faces. Clearly, the set $\mathcal{S}$ is
finite. We may present it as the disjoint union
$\mathcal{S}=\mathcal{S}_{1}\sqcup\mathcal{S}_{2}$ where any
$S\in\mathcal{S}_{1}$ satisfies $\tilde{\mu}(S)\geq 1/2+\epsilon$ while for
$S\in\mathcal{S}_{2}$ one has $\tilde{\mu}(S)<1/2+\epsilon$. By Lemma 1.1, a
random 2-complex $Y\in Y(n,p)$ contain as subcomplexes complexes
$S\in\mathcal{S}_{2}$ with probability tending to zero as $n\to\infty$. Hence,
$Y\in Y(n,p)$ may contain as subcomplexes only complexes
$S\in\mathcal{S}_{1}$, a.a.s. By Theorem 6.2, any $S\in\mathcal{S}_{1}$
satisfies $I(S)\geq C_{\epsilon}$. Hence we see that with probability tending
to one, any subcomplex $S$ of $Y$ having at most $44^{3}\cdot
C_{\epsilon}^{-2}$ faces satisfies $I(S)\geq C_{\epsilon}$. Now applying
Theorem 6.1 we obtain $I(Y^{\prime})\geq C_{\epsilon}\cdot
44^{-1}=c_{\epsilon}$, for any subcomplex $Y^{\prime}\subset Y$, a.a.s. ∎

###  6.1 Proof of Theorem 6.2

######  Definition 6.3.

We will say that a finite 2-complex $X$ is tight if for any proper subcomplex
$X^{\prime}\subset X$, $X^{\prime}\not=X$, one has $I(X^{\prime})>I(X).$

Clearly, one has

$\displaystyle I(X)\geq\min\\{I(Y)\\}$ (26)

where $Y\subset X$ is a tight subcomplex. Since
$\tilde{\mu}(Y)\geq\tilde{\mu}(X)$ for $Y\subset X$, it is obvious from (26)
that it is enough to prove Theorem 6.2 under the additional assumption that
$X$ is tight.

######  Remark 6.4.

Suppose that $X$ is pure and tight and suppose that $\gamma:S^{1}\to X$ is a
simplicial loop with $|\gamma|\cdot A_{X}(\gamma)^{-1}$ less than the minimum
of the numbers $I(X^{\prime})$ where $X^{\prime}\subset X$ is a proper
subcomplex. Let $b:D^{2}\to X$ be a minimal spanning disc for $\gamma$; then
$b(D^{2})=X,$ i.e. $b$ is surjective. Indeed, if the image of $b$ does not
contain a 2-simplex $\sigma$ then removing it we obtain a subcomplex
$X^{\prime}\subset X$ with $A_{X^{\prime}}(\gamma)=A_{X}(\gamma)$ and hence
$I(X^{\prime})\leq|\gamma|\cdot A_{X}(\gamma)^{-1}$ contradicting the
assumption on $\gamma$.

######  Lemma 6.5.

If $X$ is a tight complex with $\tilde{\mu}(X)>1/2$ then $b_{2}(X)=0$.

###### Proof.

Assume that $b_{2}(X)\not=0$. Then there exists a minimal cycle $Z\subset X$
satisfying $\mu(Z)>1/2$. Hence, by Corollary 2.6, we may find a 2-simplex
$\sigma\subset Z\subset X$ such that $\partial\sigma$ is null-homotopic in
$Z-\sigma\subset X-\sigma=X^{\prime}$. Note that $X^{\prime(1)}=X^{(1)}$ and a
simplicial curve $\gamma:S^{1}\to X^{\prime}$ is null-homotopic in
$X^{\prime}$ if and only if it is null-homotopic in $X$. Besides,
$A_{X}(\gamma)\leq A_{X^{\prime}}(\gamma)$ and hence

$\frac{|\gamma|}{A_{X}(\gamma)}\geq\frac{|\gamma|}{A_{X^{\prime}}(\gamma)},$

which implies that $I(X)\geq I(X^{\prime})>I(X)$ – contradiction. ∎

######  Lemma 6.6.

Given $\epsilon>0$ there exists a constant $C^{\prime}_{\epsilon}>0$ such that
for any finite pure tight connected 2-complex with $\tilde{\mu}(X)\geq
1/2+\epsilon$ and $L(X)\leq 0$ one has $I(X)\geq C^{\prime}_{\epsilon}$.

This Lemma is similar to Theorem 6.2 but it has an additional assumption that
$L(X)\leq 0$. It is clear from the proof that the assumption $L(X)\leq 0$ can
be replaced by any assumption of the type $L(X)\leq 1000$, i.e. by any
specific upper bound, without altering the proof.

###### Proof.

We show that the number of isomorphism types of complexes $X$ satisfying the
conditions of the Lemma is finite; hence the statement of the Lemma follows by
setting $C^{\prime}_{\epsilon}=\min I(X)$ and using Corollary 2.10 which gives
$I(X)>0$ (since $\pi_{1}(X)$ is hyperbolic) and hence
$C^{\prime}_{\epsilon}>0$. The inequality

$\mu(X)=\frac{1}{2}+\frac{2\chi(X)+L(X)}{2f(X)}\geq\frac{1}{2}+\epsilon$

is equivalent to

$f(X)\leq\epsilon^{-1}\cdot(\chi(X)+L(X)/2),$

where $f(X)$ denotes the number of 2-simplexes in $X$. By Lemma 6.5 we have
$\chi(X)=1-b_{1}(X)\leq 1$ and using the assumption $L(X)\leq 0$ we obtain
$f(X)\leq\epsilon^{-1}.$ This implies the finiteness of the set of possible
isomorphism types of $X$ and completes the proof. ∎

We will also use a relative isoperimetric constant
$I(X,X^{\prime})\in{\mathbf{R}}$ for a pair consisting of a finite 2-complex
$X$ and its subcomplex $X^{\prime}\subset X$ which will be defined as the
infimum of all ratios ${|\gamma|}\cdot{A_{X}(\gamma)}^{-1}$ where
$\gamma:S^{1}\to X^{\prime}$ runs over simplicial loops in $X^{\prime}$ which
are null-homotopic in $X$. Clearly, $I(X,X^{\prime})\geq I(X)$ and
$I(X,X^{\prime})=I(X)$ if $X^{\prime}=X$. Below is a useful strengthening of
Lemma 6.6.

######  Lemma 6.7.

Given $\epsilon>0$, let $C^{\prime}_{\epsilon}>0$ be the constant given by
Lemma 6.6. Then for any finite pure tight connected 2-complex with
$\tilde{\mu}(X)\geq 1/2+\epsilon$ and for a connected subcomplex
$X^{\prime}\subset X$ satisfying $L(X^{\prime})\leq 0$ one has
$I(X,X^{\prime})\geq C^{\prime}_{\epsilon}$.

###### Proof.

We show below that under the assumptions on $X$, $X^{\prime}$ one has

$\displaystyle I(X,X^{\prime})\geq\min_{Y}I(Y)$ (27)

where $Y$ runs over all subcomplexes $X^{\prime}\subset Y\subset X$ satisfying
$L(Y)\leq 0$. Clearly, $\tilde{\mu}(Y)\geq 1/2+\epsilon$ for any such $Y$. In
the proof of Lemma 6.6 we showed that $b_{2}(X)=0$ which implies that
$b_{2}(Y)=0$. Besides, without loss of generality we may assume that $Y$ is
connected. The arguments of the proof of Lemma 6.6 now apply (i.e. $Y$ may
have finitely many isomorphism types, each having a hyperbolic fundamental
group) and the result follows $I(X,X^{\prime})\geq\min_{Y}I(Y)\geq
C^{\prime}_{\epsilon}$.

Suppose that inequality (27) is false, i.e. $I(X,X^{\prime})<\min_{Y}I(Y)$,
and consider a simplicial loop $\gamma:S^{1}\to X^{\prime}$ satisfying
$\gamma\sim 1$ in $X$ and $|\gamma|\cdot A_{X}(\gamma)^{-1}<\min_{Y}I(Y).$ Let
$\psi:D^{2}\to X$ be a simplicial spanning disc of minimal area. It follows
from the arguments of Ronan [16], that $\psi$ is non-degenerate in the
following sense: for any 2-simplex $\sigma$ of $D^{2}$ the image
$\psi(\sigma)$ is a 2-simplex and for two distinct 2-simplexes
$\sigma_{1},\sigma_{2}$ of $D^{2}$ with $\psi(\sigma_{1})=\psi(\sigma_{2})$
the intersection $\sigma_{1}\cap\sigma_{2}$ is either $\emptyset$ or a vertex
of $D^{2}$. In other words, we exclude foldings, i.e. situations such that
$\psi(\sigma_{1})=\psi(\sigma_{2})$ and $\sigma_{1}\cap\sigma_{2}$ is an edge.
Consider $Z=X^{\prime}\cup\psi(D^{2})$. Note that $L(Z)\leq 0$. Indeed, since

$L(Z)=\sum_{e}(2-\deg_{Z}(e)),$

where $e$ runs over the edges of $Z$, we see that for $e\subset X^{\prime}$,
$\deg_{X^{\prime}}(e)\leq\deg_{Z}(e)$ and for a newly created edges
$e\subset\psi(D^{2})$, clearly $\deg_{Z}(e)\geq 2$. Hence, $L(Z)\leq
L(X^{\prime})\leq 0$. On the other hand, $A_{X}(\gamma)=A_{Z}(\gamma)$ and
hence $I(Z)\leq|\gamma|\cdot A_{X}(\gamma)^{-1}<\min_{Y}I(Y)$, a
contradiction. ∎

The main idea of the proof of Theorem 6.2 in the general case is to find a
planar complex (a “singular surface”) $\Sigma$ with one boundary component
$\partial_{+}\Sigma$ being the initial loop and such that “the rest of the
boundary” $\partial_{-}\Sigma$ is a “product of negative loops” (i.e. loops
satisfying Lemma 6.7). The essential part of the proof is in estimating the
area (the number of 2-simplexes) of such $\Sigma$.

###### Proof of Theorem 6.2.

Consider a connected tight pure 2-complex $X$ satisfying

$\displaystyle\tilde{\mu}(X)\geq\frac{1}{2}+\epsilon$ (28)

and a simplicial prime loop $\gamma:S^{1}\to X$ such that the ratio
$|\gamma|\cdot A_{X}(\gamma)^{-1}$ is less than the minimum of the numbers
$I(X^{\prime})$ for all proper subcomplexes $X^{\prime}\subset X$. Consider a
minimal spanning disc $b:D^{2}\to X$ for $\gamma=b|_{\partial D^{2}}$; here
$D^{2}$ is a triangulated disc and $b$ is a simplicial map. As we showed in
Remark 6.4, the map $b$ is surjective. As explained in the proof of Lemma 6.7,
due to arguments of Ronan [16], we may assume that $b$ has no foldings.

For any integer $i\geq 1$ we denote by $X_{i}\subset X$ the pure subcomplex
generated by all 2-simplexes $\sigma$ of $X$ such that the preimage
$b^{-1}(\sigma)\subset D^{2}$ contains $\geq i$ two-dimensional simplexes. One
has $X=X_{1}\supset X_{2}\supset X_{3}\supset\dots.$ Each $X_{i}$ may have
several connected components and we will denote by $\Lambda$ the set labelling
all the connected components of the disjoint union $\sqcup_{i\geq 1}X_{i}$.
For $\lambda\in\Lambda$ the symbol $X_{\lambda}$ will denote the corresponding
connected component of $\sqcup_{i\geq 1}X_{i}$ and the symbol
$i=i(\lambda)\in\\{1,2,\dots\\}$ will denote the index $i\geq 1$ such that
$X_{\lambda}$ is a connected component of $X_{i}$, viewed as a subset of
$\sqcup_{i\geq 1}X_{i}$. We endow $\Lambda$ with the following partial order:
$\lambda_{1}\leq\lambda_{2}$ iff $X_{\lambda_{1}}\supset X_{\lambda_{2}}$
(where $X_{\lambda_{1}}$ and $X_{\lambda_{2}}$ are viewed as subsets of $X$)
and $i(\lambda_{1})\leq i(\lambda_{2})$.

Next we define the sets

$\Lambda^{-}=\\{\lambda\in\Lambda;L(X_{\lambda})\leq 0\\}$

and

$\Lambda^{+}=\\{\lambda\in\Lambda;\mbox{for any $\mu\in\Lambda$ with
$\mu\leq\lambda$, }\,L(X_{\mu})>0\\}.$

Finally we consider the following subcomplex of the disk $D^{2}$:

$\displaystyle\Sigma^{\prime}=D^{2}-\bigcup_{\lambda\in\Lambda^{-}}{\rm{Int}}(b^{-1}(X_{\lambda}))$
(29)

and we shall denote by $\Sigma$ the connected component of $\Sigma^{\prime}$
containing the boundary circle $\partial D^{2}$.

Recall that for a 2-complex $X$ the symbol $f(X)$ denotes the number of
2-simplexes in $X$. We have

$\displaystyle f(D^{2})=\sum_{\lambda\in\Lambda}f(X_{\lambda}),$ (30)

and

$\displaystyle f(\Sigma)\leq
f(\Sigma^{\prime})\leq\sum_{\lambda\in\Lambda^{+}}f(X_{\lambda}).$ (31)

Formula (30) follows from the observation that any 2-simplex of $X=b(D^{2})$
contributes to the RHS of (30) as many units as its multiplicity (the number
of its preimages under $b$). Formula (31) follows from (30) and from the fact
that for a 2-simplex $\sigma$ of $\Sigma^{\prime}$ the image $b(\sigma)$ lies
always in the complexes $X_{\lambda}$ with $L(X_{\lambda})>0$.

Figure 7: The complex $\Sigma\subset D^{2}$.

######  Lemma 6.8.

One has the following inequality

$\displaystyle\sum_{\lambda\in\Lambda^{+}}L(X_{\lambda})\leq|\partial D^{2}|.$
(32)

###### Proof.

For an edge $e$ of $X$ and for $\lambda\in\Lambda$ we denote

$\widetilde{\deg}_{\lambda}(e)=\left\\{\begin{array}[]{lll}2-\deg_{X_{\lambda}}(e),&\mbox{if}&e\subset
X_{\lambda},\\\ 0,&\mbox{if}&e\not\subset X_{\lambda}.\end{array}\right.$

Note that $\widetilde{\deg}_{\lambda}(e)\leq 1$ and
$\widetilde{\deg}_{\lambda}(e)=1$ iff $e$ belongs to a unique 2-simplex of
$X_{\lambda}$, i.e. $e\subset\partial X_{\lambda}$. One has

$\displaystyle\sum_{\lambda\in\Lambda^{+}}L(X_{\lambda})=\sum_{e\subset
X}\sum_{\lambda\in\Lambda^{+}}\widetilde{\deg}_{\lambda}(e)$
$\displaystyle\leq$ $\displaystyle\sum_{e\subset
X}\max\left\\{\sum_{\Lambda^{+}}\widetilde{\deg}_{\lambda}(e),0\right\\}$ (33)
$\displaystyle\leq$ $\displaystyle\sum_{e\subset
X}\max\left\\{\sum_{\Lambda}\widetilde{\deg}_{\lambda}(e),0\right\\}$
$\displaystyle\leq$ $\displaystyle\sum_{e\subset X}|b^{-1}(e)\cap\partial
D^{2}|=|\partial D^{2}|.$ (34)

Here $|b^{-1}(e)\cap\partial D^{2}|$ denotes the number of boundary edges
which $b$ maps onto the edge $e$. The inequality (33) follows from the fact
that $\lambda\mapsto\widetilde{\deg}_{\lambda}(e)$ is a non-decreasing
function on the poset $\Lambda_{e}=\\{\lambda\in\Lambda;e\subset
X_{\lambda}\\}$. Note that $\Lambda_{e}$ is in fact linearly ordered. Indeed,
suppose that $\lambda_{1},\lambda_{2}\in\Lambda_{e}$ are such that
$i_{1}=i(\lambda_{1})\geq i_{2}=i(\lambda_{2})$. Then $X_{\lambda_{2}}$, as a
path-component of $X_{i_{2}}$, is contained in a path-component of
$X_{i_{1}}$; the latter must coincide with $X_{\lambda_{1}}$ since the
intersection $X_{\lambda_{1}}\cap X_{\lambda_{2}}\not=\emptyset$ is nonempty
(since it contains the edge $e$). Thus we see that the assumption
$i(\lambda_{1})\geq i(\lambda_{2})$ implies that $X_{\lambda_{2}}\subset
X_{\lambda_{1}}$, i.e. $\lambda_{1}\geq\lambda_{2}$. Denoting
$\Lambda_{e}\cap\Lambda^{+}=\Lambda_{e}^{+}$ we observe that if the sum

$\displaystyle\sum_{\Lambda^{+}}\widetilde{\deg}_{\lambda}(e)=\sum_{\Lambda^{+}_{e}}\widetilde{\deg}_{\lambda}(e)>0$
(35)

is positive then (due to the monotonicity) one has
$\widetilde{\deg}_{\lambda_{0}}(e)>0$ for the maximal element $\lambda_{0}$ of
$\Lambda_{e}^{+}$ and hence $\widetilde{\deg}_{\lambda}(e)>0$ for all
$\lambda\geq\lambda_{0}$, $\lambda\in\Lambda_{e}$. Thus, the positivity (35)
implies
$\sum_{\Lambda^{+}}\widetilde{\deg}_{\lambda}(e)<\sum_{\Lambda}\widetilde{\deg}_{\lambda}(e)$
giving (33).

To prove the inequality (34) we observe that for an edge $e$ of $X$ one has

$\displaystyle\sum_{\lambda\in\Lambda}\deg_{X_{\lambda}}(e)=\sum_{e^{\prime}\in
b^{-1}(e)}\deg_{D^{2}}(e^{\prime})=2|b^{-1}(e)|-|b^{-1}(e)\cap\partial D^{2}|$
(36)

and hence

$\displaystyle\sum_{\lambda\in\Lambda}\widetilde{\deg}_{\lambda}(e)$
$\displaystyle=$ $\displaystyle
2\cdot|\Lambda^{e}|-\sum_{\lambda\in\Lambda}\deg_{\lambda}(e)$
$\displaystyle\leq$ $\displaystyle
2\cdot|b^{-1}(e)|-\sum_{\lambda\in\Lambda}\deg_{\lambda}(e)$ $\displaystyle=$
$\displaystyle|b^{-1}(e)\cap\partial D^{2}|\,\,\,\mbox{(using (\ref{11}))}.$

Inequality (6.1) is based on

$\displaystyle|\Lambda_{e}|\,=\,\max_{\sigma\supset
e}|b^{-1}(\sigma)|\,\leq\,|b^{-1}(e)|,$ (38)

where $\sigma$ runs over all 2-simplexes of $X$ containing $e$. The equality
which appears in (38) is a consequence of the set $\Lambda_{e}$ being linearly
ordered, see above. This completes the proof. ∎

Now we continue with the proof of Theorem 6.2. Consider a tight pure 2-complex
$X$ satisfying (28) and a simplicial loop $\gamma:S^{1}\to X$ as above. We
will use the notation introduced earlier. The complex $\Sigma$ is a connected
subcomplex of the disk $D^{2}$; it contains the boundary circle $\partial
D^{2}$ which we will denote also by $\partial_{+}\Sigma$. The closure of the
complement of $\Sigma$,

$N=\overline{D^{2}-\Sigma}\subset D^{2}$

is a pure 2-complex. Let $N=\cup_{j\in J}N_{j}$ be the strongly connected
components of $N$. Each $N_{j}$ is PL-homeomorphic to a disc and we define

$\partial_{-}\Sigma=\cup_{j\in J}\partial N_{j},$

the union of the circles $\partial N_{j}$ which are the boundaries of the
strongly connected components of $N$. It may happen that $\partial_{+}\Sigma$
and $\partial_{-}\Sigma$ have nonempty intersection. Also, the circles forming
$\partial_{-}\Sigma$ may not be disjoint.

We claim that for any $j\in J$ there exists $\lambda\in\Lambda^{-}$ such that
$b(\partial N_{j})\subset X_{\lambda}$. Indeed, let
$\lambda_{1},\dots,\lambda_{r}\in\Lambda^{-}$ be the minimal elements of
$\Lambda^{-}$ with respect to the partial order introduced earlier. The
complexes $X_{\lambda_{1}},\dots,X_{\lambda_{r}}$ are connected and pairwise
disjoint and for any $\lambda\in\Lambda^{-}$ the complex $X_{\lambda}$ is a
subcomplex of one of the sets $X_{\lambda_{i}}$, where $i=1,\dots,r$. From our
definition (29) it follows that the image of the circle $b(\partial N_{j})$ is
contained in the union $\cup_{i=1}^{r}X_{\lambda_{i}}$ but since $b(\partial
N_{j})$ is connected it must lie in one of the sets $X_{\lambda_{i}}$.

We may apply Lemma 6.7 to each of the circles $\partial N_{j}$. We obtain that
each of the circles $\partial N_{j}$ admits a spanning discs of area $\leq
K_{\epsilon}|\partial N_{j}|$, where $K_{\epsilon}=C^{\prime-1}_{\epsilon}$ is
the inverse of the constant given by Lemma 6.7. Using the minimality of the
disc $D^{2}$ we obtain that the circles $\partial N$ bound in $D^{2}$ several
discs with the total area $A\leq K_{\epsilon}\cdot|\partial_{-}\Sigma|$ (here
we use Lemma 6.6); otherwise one could reduce the area of the initial disc.

For $\lambda\in\Lambda^{+}$ one has $L(X_{\lambda})\geq 1$ and
$\chi(X_{\lambda})\leq 1$ (since $b_{2}(X_{\lambda})=0$), hence we have

$3L(X_{\lambda})\geq 2\chi(X_{\lambda})+L(X_{\lambda})\geq 2\epsilon
f(X_{\lambda})$

where on the last stage we used the inequality $\mu(X_{\lambda})\geq
1/2+\epsilon$. Summing up we get

$f(\Sigma)\leq\sum_{\lambda\in\Lambda^{+}}f(X_{\lambda})\leq\frac{3}{2\epsilon}\sum_{\lambda\in\Lambda^{+}}L(X_{\lambda})\leq\frac{3}{2\epsilon}|\partial
D^{2}|.$

The rightmost inequality is given by Lemma 6.8.

Next we observe, that

$\displaystyle|\partial_{-}\Sigma|\leq 2f(\Sigma)+|\partial_{+}\Sigma|.$ (39)

To explain this inequality we note that each edge of $\partial_{-}\Sigma$
which does not belong to $\partial_{+}\Sigma$ is incident to a face of
$\Sigma$ and a face of $\Sigma$ can have at most two edges lying on
$\partial_{-}\Sigma$. Therefore, we obtain

$\displaystyle f(D^{2})$ $\displaystyle\leq$ $\displaystyle
f(\Sigma)+A\,\leq\,\frac{3}{2\epsilon}|\gamma|+K_{\epsilon}\cdot 2\cdot
f(\Sigma)+K_{\epsilon}|\gamma|$ $\displaystyle\leq$
$\displaystyle\left(\frac{3}{2\epsilon}(1+2K_{\epsilon})+K_{\epsilon}\right)\cdot|\gamma|,$

implying

$\displaystyle I(X)\geq\frac{2\epsilon}{3+6K_{\epsilon}+2\epsilon
K_{\epsilon}}.$ (40)

This completes the proof of Theorem 6.2. ∎

## References

  * [1] L. Aronshtam, N. Linial, T. Łuczak, R. Meshulam, Collapsibility and vanishing of top homology in random simplicial complexes, Discrete Comput. Geom. 49 (2013), no. 2, 317 334.
  * [2] E. Babson, C. Hoffman, M. Kahle, The fundamental group of random $2$-complexes, J. Amer. Math. Soc. 24 (2011), 1-28. See also the latest archive version arXiv:0711.2704 revised on 20.09.2012.
  * [3] W. A. Bogley, J.H.C. Whitehead’s asphericity question, in: ”Two-dimensional Homotopy and Combinatorial Group Theory”, eds. C. Hog-Angeloni, A. Sieradski and W. Metzler, LMS Lecture Notes 197, Cambridge Univ Press (1993), 309-334.
  * [4] W.H. Cockcroft, On two-dimensional aspherical complexes, Proc. London Math. Soc. 4(1954), 375-384.
  * [5] D. Cohen, A.E. Costa, M. Farber, T. Kappeler, Topology of random 2-complexes, Journal of Discrete and Computational Geometry, 47(2012), 117-149.
  * [6] A.E. Costa, M. Farber, The asphericity of random 2-dimensional complexes, to appear in Random Structures and Algorithms, preprint arXiv:1211.3653v1
  * [7] P. Erdős, A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 17–61.
  * [8] M. Gromov, Filling Riemannian manifolds, J. Differential Geometry, 18(1983), 1–147.
  * [9] M. Gromov, Hyperbolic groups, in Essays in group theory, ed. S. M. Gersten, Springer (1987), 75-265.
  * [10] S. Janson, T. Łuczak, A. Ruciński, Random graphs, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley-Interscience, New York, 2000.
  * [11] M.G. Katz, Y.B. Rudyak, S. Sabourau, Systoles of 2-complexes, Reeb graphs, and Grushko decomposition, IMRN 2006, pp.1–30.
  * [12] D. Kozlov, The threshold function for vanishing of the top homology group of random $d$-complexes, Proc. Amer. Math. Soc. 138 (2010), 4517-4527.
  * [13] N. Linial, R. Meshulam, Homological connectivity of random $2$-complexes, Combinatorica 26 (2006), 475–487.
  * [14] R. Meshulam, N. Wallach, Homological connectivity of random $k$-complexes, Random Structures & Algorithms 34 (2009), 408–417.
  * [15] P. Papasoglu, Cheeger constants of surfaces and isoperimetric inequalities, Transactions of the AMS 361(2009), pp. 5139-5162.
  * [16] M.A. Ronan, On the second homotopy group of certain simplicial complexes and some combinatorial applications, Quart. J. Math. 32(1981), 225 - 233.
  * [17] S. Rosenbrock, The Whitehead Conjecture - an overview, Siberian Electronoc Mathematical Reports, 4(2007), 440-449.

A.E. Costa, Warwick Mathematics Institute, Warwick University, Coventry CV4
7AL, UK

email<EMAIL_ADDRESS>

M. Farber, Warwick Mathematics Institute, Warwick University, Coventry CV4
7AL, UK

email<EMAIL_ADDRESS>