# The homotopical dimension of random 2-complexes

Daniel C. Cohen, Michael Farber and Thomas Kappeler Partially supported by
Louisiana Board of Regents grant NSF(2010)-PFUND-171.Partially supported by a
grant from the EPSRC.Partially supported by the Swiss National Science
Foundation.

###### Abstract

Stochastic algebraic topology aims at studying random or partly known spaces
which typically arise in applications as configuration spaces of large
systems. In this paper we study the Linial–Meshulam model of random two-
dimensional complexes. We prove that if the probability parameter $p$
satisfies $p\ll n^{-1-\epsilon}$, where $\epsilon>0$ is arbitrary and
independent of $n$, then a random 2-complex $Y$ is homotopically one
dimensional with probability tending to $1$ as $n\to\infty$. More precisely,
we show that under this assumption on $p$, the complex $Y$ can be collapsed to
a graph in finitely many steps. It is known that the homotopical dimension of
$Y$ is equal to $2$ for $p>3n^{-1}$.

##  1 Introduction

Since its inception in 1959 by Erdös and Rényi [ER60], the theory of random
graphs has developed into a rapidly growing and widely applicable branch of
discrete mathematics, bringing together ideas from graph theory,
combinatorics, and probability theory. In one model, a random graph is a
subgraph $\Gamma$ of a complete graph on $n$ vertices such that every edge of
the complete graph is included in $\Gamma$ with probability $p$, independently
of the other edges. One is interested in probabilistic features of $\Gamma$
and their dependence on $p$ when $n$ is large. Here $0<p<1$ is a probability
parameter which in general may depend on $n$. The theory of random graphs
[AS00, Bol08, JŁR00] offers many spectacular results and predictions, which
play an essential role in various engineering and computer science
applications. Random graphs also serve within mathematics as accessible models
for other, more complex random structures.

Higher dimensional analogs of the aforementioned Erdős–Rényi model were
recently suggested and studied by Linial–Meshulam in [LM06], and
Meshulam–Wallach in [MW09]. In these models, one generates a random
$d$-dimensional simplicial 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$. Note that
in this construction $Y$ contains the $(d-1)$-dimensional skeleton of
$\Delta_{n}$. 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 [Koz09].

In this paper, we focus on 2-dimensional random complexes. The corresponding
probability space $G(\Delta_{n}^{(2)},p)$ of the Linial–Meshulam model is
defined as follows. Let $\Delta_{n}$ denote the $(n-1)$-dimensional simplex
with vertices $\\{1,2,\dots,n\\}$. Then $G(\Delta_{n}^{(2)},p)$ denotes the
set of all 2-dimensional subcomplexes

$\Delta_{n}^{(1)}\subset Y\subset\Delta_{n}^{(2)},$

containing the one-dimensional skeleton $\Delta_{n}^{(1)}$. The probability
function $\mathbb{P}:G(\Delta_{n}^{(2)},p)\to{\mathbf{R}}$ is given by the
formula

$\mathbb{P}(Y)=p^{f(Y)}(1-p)^{{n\choose 3}-f(Y)},\quad Y\in
G(\Delta_{n}^{(2)},p),$

where $f(Y)$ denotes the number of faces in $Y$. In other words, each of the
2-dimensional simplexes of $\Delta_{n}^{(2)}$ is included in a random
2-complex $Y$ with probability $p$, independently of the other 2-simplexes. As
in the case of random graphs, $0<p<1$ is a probability parameter which may
depend on $n$. When $n$ grows, the model $G(\Delta_{n}^{(2)},p)$ includes all
finite $2$-dimensional complexes containing the full 1-skeleton
$\Delta_{n}^{(1)}$; however, the likelihood of various topological phenomena
is dependent on the value of $p$. The theory of deterministic 2-complexes
itself is a rich and active field of current research with many challenging
open questions, see [HMS93].

The fundamental group of a random 2-complex $Y\in G(\Delta_{n}^{(2)},p)$ was
investigated by Babson, Hoffman, and Kahle [BHK08]. They showed that for $p\gg
n^{-1/2}\cdot(3\log n)^{1/2}$, the group $\pi_{1}(Y)$ vanishes asymptotically
almost surely (i.e., the probability that $\pi_{1}(Y)$ is trivial tends to $1$
as $n\to\infty$). For $p\ll n^{-1/2-\epsilon}$, these authors use notions of
negative curvature due to Gromov to study the nontriviality and hyperbolicity
of $\pi_{1}(Y)$.

In this paper, we show that for $p\ll n^{-1-\epsilon}$ a random 2-complex $Y$
is homotopically 1-dimensional, a.a.s.111We use the abbreviation a.a.s. for
the phrase “asymptotically almost surely”. More precisely, we show that $Y$
can be collapsed to a graph in finitely many steps. This implies that $Y$ has
a free fundamental group and vanishing 2-dimensional homology. Note that the
vanishing of 2-dimensional homology in this range of $p$ also follows from a
result of Kozlov [Koz09]. In [CFK10], it is shown that for $p>3/n$, the
homology group $H_{2}(Y;{\mathbf{Z}})$ is nontrivial with probability tending
to $1$; see also [Koz09]. Thus, for $p>3/n$, the random 2-complex $Y$ is
homotopically two-dimensional a.a.s.

Our main result is as follows:

######  Theorem 1.

(a) If for some $k\geq 1$ the probability parameter $p$ satisfies222Recall
that the symbol $a_{n}\ll b_{n}$ means that $a_{n}>0$ and $a_{n}/b_{n}\to 0$
as $n\to\infty$.

$p\ll n^{-1-\frac{2}{k+1}},$

then a random 2-complex $Y\in G(\Delta_{n}^{(2)},p)$ is collapsible to a graph
in at most $k$ steps, asymptotically almost surely (a.a.s). (b) If for some
$k\geq 1$ the probability parameter $p$ satisfies

$p\gg n^{-1-\frac{1}{3\cdot 2^{k-1}-1}},$

then $Y$ is not collapsible to a graph in $k$ or fewer steps, a.a.s.

Loosely speaking, Theorem 1 combines with previously known results to suggest
that a random 2-complex with vanishing 2-dimensional homology is homotopically
one-dimensional.

Theorem 1 implies:

######  Corollary 2.

If for some $k\geq 1$ the probability parameter $p$ satisfies

$p\ll n^{-1-\frac{2}{k+1}}$

then the fundamental group $\pi_{1}(Y)$ of a random 2-complex $Y\in
G(\Delta_{n}^{(2)},p)$ is free and $H_{2}(Y;{\mathbf{Z}})=0$, a.a.s.

The proof of Theorem 1 is given at the very end of the paper. A key role is
played by Theorem 13, which states that there exists a finite list of
forbidden 2-complexes $\mathcal{L}_{k,r}$ with $k\geq 0$ and $r\geq 2$, such
that an arbitrary 2-complex of degree at most $r$ (see below) is collapsible
to a graph in $k$ steps if and only if it does not contain any of the
2-complexes from $\mathcal{L}_{k,r}$. This allows us to reduce the
collapsiblity problem to the containment problem for random complexes which
was studied in [CFK10].

### Acknowledgments

This research was implemented during visits of M. Farber to FIM ETH Zürich and
Louisiana State University, and a visit of D. Cohen to the University of
Zürich. Portions of this work were carried out during the Spring of 2010, when
the first two authors participated in the Mathematisches Forschungsinstitut
Oberwolfach Research in Pairs program. We thank the FIM ETH, LSU, the
University of Zürich, and the MFO for their support and hospitality, and for
providing productive mathematical environments.

##  2 Collapsibility of a 2-complex to a graph

###  2.1 Basic definitions

Let $Y$ be a finite 2-dimensional simplicial complex. An edge of $Y$ is called
free if it is included in exactly one 2-simplex.

The boundary $\partial Y$ is defined as the union of free edges. We say that a
2-complex $Y$ is closed if $\partial Y=\emptyset$.

A $2$-complex $Y$ is called pure if every maximal simplex is 2-dimensional. By
the pure part of a 2-complex we mean the maximal pure subcomplex, i.e. the
union of all 2-simplexes.

Let $Y$ be a simplicial 2-complex and let $\sigma$ and $\tau$ be two
2-simplexes of $Y$. We say that $\sigma$ and $\tau$ are adjacent if they
intersect in an edge. The distance between $\sigma$ and $\tau$,
$d_{Y}(\sigma,\tau)$, is the minimal integer $k$ such that there exists a
sequence of 2-simplexes $\sigma=\sigma_{0},\sigma_{1},\dots,\sigma_{k}=\tau$
with the property that $\sigma_{i}$ is adjacent to $\sigma_{i+1}$ for every
$0\leq i<k$. (If no such sequence exists then $d_{Y}(\sigma,\tau)=\infty$.)
The diameter  ${\rm{diam}}(Y)$ is defined as the maximal value of
$d_{Y}(\sigma,\tau)$ taken over pairs of 2-simplexes of $Y$.

A simplicial 2-complex is strongly connected if it has a finite diameter.

A simplicial 2-complex has degree $\leq r$ if every edge is incident to at
most $r$ 2-simplexes.

A pseudo-surface is a finite, pure, strongly connected 2-dimensional
simplicial complex of degree at most $2$ (i.e., every edge is included in at
most two 2-simplexes).

More generally, for an integer $r>0$, an $r$-pseudo-surface is a finite, pure,
strongly connected 2-dimensional simplicial complex of degree at most $r$.

###  2.2 Simplicial collapse

Let $Y$ be a 2-complex. A 2-simplex of $Y$ is called free if at least one of
its edges is free. Let $\sigma_{1},\dots,\sigma_{k}$ be all free 2-simplexes
in $Y$, and let $e_{1},\dots,e_{k}$ be free edges with
$e_{i}\subset\sigma_{i}$. We say that the complex

$Y^{\prime}={Y-\cup_{i=1}^{k}{\rm{int}}(\sigma_{i})-\cup_{i=1}^{k}{\rm{int}}(e_{i})}$

is obtained from $Y$ by collapsing all free 2-simplexes. Clearly
$Y^{\prime}\subset Y$ is a deformation retract. The operation $Y\searrow
Y^{\prime}$ is called a simplicial collapse. Note that $Y^{\prime}$ is not
uniquely determined if one of the free simplexes of $Y$ has two free edges;
however the pure part of $Y^{\prime}$ (i.e. the union of 2-simplexes of
$Y^{\prime}$) is uniquely determined.

This process can be iterated $Y^{\prime}\searrow Y^{\prime\prime}$,
$Y^{\prime\prime}\searrow Y^{\prime\prime\prime}$, etc. We denote $Y=Y^{(0)}$,
$Y^{\prime}=Y^{(1)}$, $Y^{\prime\prime}=Y^{(2)}$ etc. The sequence of
subcomplexes $Y^{(0)}\supset Y^{(1)}\supset Y^{(2)}\supset\dots$ is decreasing
and there are two possibilities: either (a) for some $k$, the complex
$Y^{(k)}$ is one-dimensional (a graph), or (b) for some $k$, the complex
$Y^{(k)}$ is 2-dimensional and closed, i.e., $\partial Y^{(k)}=\emptyset$.

######  Definition 3.

We say that $Y$ is collapsible to a graph in at most $k$ steps if $Y^{(k)}$ is
a graph. We say that $Y$ is collapsible to a graph in $k$ steps if $Y^{(k)}$
is a graph and $\dim Y^{(k-1)}=2$.

Observe that if $Y$ is collapsible to a graph in at most $k$ steps then any
simplicial subcomplex $S\subset Y$ is also collapsible to a graph in at most
$k$ steps. At each step one removes the free triangles in $Y^{(i)}$ which
belong to $S$.

Let $Y$ be a 2-complex, and consider the sequence of collapses

$Y^{(0)}\searrow Y^{(1)}\searrow Y^{(2)}\searrow\dots\searrow
Y^{(k)}\searrow\dots.$

For a 2-simplex $\sigma\in Y$ define

$D_{Y}(\sigma)=\sup\\{i;\,\sigma\subset
Y^{(i)}\\}\,\,\in\\{0,1,\dots,\infty\\}.$

A 2-simplex $\sigma$ is free if and only if $D_{Y}(\sigma)=0$.

A 2-complex $Y$ is collapsible to a graph in at most $k+1$ steps if and only
if $D_{Y}(\sigma)\leq k$ for any $2$-simplex $\sigma$. If after performing
several collapses $Y^{(0)}\searrow Y^{(1)}\searrow Y^{(2)}\searrow\dots$ we
obtain a subcomplex $Y^{(r)}\subset Y$ with empty boundary $\partial
Y^{(r)}=\emptyset$, then $Y^{(r)}=Y^{(r+1)}=Y^{(r+2)}=\dots$ and
$D_{Y}(\sigma)=\infty$ for any simplex $\sigma$ in $Y^{(r)}$.

######  Lemma 4.

Let $\sigma$ be a 2-simplex with $D_{Y}(\sigma)=k$ where $0<k<\infty$. Then
one of the edges $e$ of $\sigma$ has the following property: for any 2-simplex
$\sigma^{\prime}$ of $Y$ which is incident to $e$ and distinct from $\sigma$
one has $D_{Y}(\sigma^{\prime})<k$ and there exists a 2-simplex
$\sigma^{\prime}$ incident to $e$ and distinct from $\sigma$ such that
$D_{Y}(\sigma^{\prime})=k-1$.

###### Proof.

Since $D_{Y}(\sigma)=k$, we know that after $k$ collapses an edge $e$ of
$\sigma$ becomes free. All other simplexes $\sigma^{\prime}$ of $Y$ incident
to $e$ must have been eliminated in previous steps, i.e., they satisfy
$D_{Y}(\sigma^{\prime})<k$. At least one of these simplexes $\sigma^{\prime}$
must have been eliminated in step $k-1$ since otherwise $\sigma$ would have
become free earlier. ∎

######  Lemma 5.

If $Z\subset Y$ is a subcomplex and $\sigma\subset Z$ is a $2$-simplex, then

$D_{Z}(\sigma)\leq D_{Y}(\sigma).$

###### Proof.

If a 2-simplex belongs to $Z$ and is not free in $Z$ then it is not free in
$Y$. This implies that $Z^{\prime}\subset Y^{\prime}$ and therefore
$Z^{(i)}\subset Y^{(i)}$ for any $i\geq 1$. Thus, the maximal $i$ such that
$\sigma$ is contained in $Z^{(i)}$ is less than or equal to the maximal $i$
such that $\sigma$ is contained in $Y$, which implies the statement of the
Lemma. ∎

###  2.3 $\sigma$-accessible boundary

######  Definition 6.

Let $Y$ be a 2-complex and let $\sigma,\tau$ be two 2-simplexes of $Y$ with
$D_{Y}(\tau)=0$ and $D_{Y}(\sigma)=k\geq 1$. A collapsing path from $\tau$ to
$\sigma$ is a sequence of 2-simplexes
$\tau=\sigma_{0},\sigma_{1},\dots,\sigma_{k-1},\sigma_{k}=\sigma$ such that
$D_{Y}(\sigma_{i})=i$ and each pair $\sigma_{i}$ and $\sigma_{i+1}$ has a
common edge, where $i=0,\dots,k-1$.

In a collapsing path, the initial simplex $\sigma_{0}=\tau$ is a free simplex,
and hence at least one of its edges belongs to the boundary $\partial Y$.

######  Definition 7.

Given a 2-simplex $\sigma$, we denote by $A_{Y}(\sigma)\subset\partial Y$ the
union of the edges in $\sigma_{0}\cap\partial Y$ which can appear in a
collapsing path $\sigma_{0},\sigma_{1},\dots,\sigma_{k}$ ending at $\sigma$.
We call $A_{Y}(\sigma)$ the $\sigma$-accessible part of the boundary.

In Definition 7, clearly $k=D_{Y}(\sigma)$. Note that
$A_{Y}(\sigma)\not=\emptyset$ if and only if $D_{Y}(\sigma)<\infty$.

######  Definition 8.

Let $\sigma$ be a 2-simplex of $Y$ with $D_{Y}(\sigma)\geq 1$. For an edge $e$
of $\sigma$ define

$A_{Y}(\sigma,e)\subset A_{Y}(\sigma)$

as the set of all edges $e^{\prime}$ of the boundary $\partial Y$ with the
property that there exists a collapsing path
$\sigma_{0},\sigma_{1},\dots,\sigma_{k}=\sigma$ such that $e^{\prime}$ is an
edge of $\sigma_{0}$ and $e=\sigma_{k-1}\cap\sigma_{k}$.

If $e_{1},e_{2},e_{3}$ are the edges of $\sigma$ then
$A_{Y}(\sigma)=\cup_{i=1}^{3}A_{Y}(\sigma,e_{i})$ and the sets
$A_{Y}(\sigma,e_{i})$ need not be mutually disjoint.

######  Lemma 9.

Let $\sigma$ and $\sigma^{\prime}$ be adjacent 2-simplexes of $Z$ with

$D_{Z}(\sigma)=D_{Z}(\sigma^{\prime})+1.$

Assume that any collapsing path in $Z$ ending at $\sigma$ passes through the
edge $e=\sigma\cap\sigma^{\prime}$. If $Z$ is embedded as a subcomplex
$Z\subset Y$ and

$D_{Z}(\sigma^{\prime})<D_{Y}(\sigma^{\prime}),$

then

$D_{Z}(\sigma)<D_{Y}(\sigma).$

###### Proof.

Let $k=D_{Z}(\sigma^{\prime})=D_{Z}(\sigma)-1$. We must show that
$D_{Y}(\sigma)\geq k+2.$ First we claim that the edge $e$ may become free only
after at least $k+2$ collapses in $Y$. Assume it is free in $Y$ after $k+1$
collapses. By assumption, $D_{Y}(\sigma^{\prime})\geq k+1.$ Hence the edge $e$
can only be free after $k+1$ collapses in $Y$ if $\sigma$ has been removed
already before, i.e., $D_{Y}(\sigma)\leq k.$ On the other hand, by Lemma 5,
$D_{Y}(\sigma)\geq D_{Z}(\sigma)=k+1$ which leads to a contradiction.

By assumption, the two edges of $\sigma$ different from $e$ are not free in
$Z^{(k+1)}$ and hence they are not free in $Y^{(k+1)}$. Thus
$D_{Y}(\sigma)\geq k+2$ as claimed. ∎

Note that the assumption of Lemma 9 that any collapsing path in $Z$ ending at
$\sigma$ passes through the edge $e$ is equivalent to
$A_{Z}(\sigma,e^{\prime})=\emptyset$ for the two remaining edges
$e^{\prime}\not=e$ of $\sigma$.

######  Lemma 10.

Let $Z\subset Y$ be a subcomplex. If $D_{Z}(\sigma)=D_{Y}(\sigma)$ for a
2-simplex $\sigma$ of $Z$ then there is an edge $e$ of $\sigma$ such that

$\emptyset\not=A_{Z}({\sigma,e})\subset A_{Y}({\sigma,e})\subset\partial Y.$

###### Proof.

Without loss of generality, we may assume that $Y$ is obtained from $Z$ by
attaching a single $2$-simplex.

The proof is by induction on $k=D_{Y}(\sigma)=D_{Z}(\sigma)$.

In the case $k=0$, there is an edge $e$ of $\sigma$ that is free in both $Z$
and $Y$. In particular, $e\subset\partial Y$.

We include the case $k=1$. Recall that $Z^{\prime}=Z^{(1)}$ denotes the result
of the first collapse of $Z$, $Z\searrow Z^{\prime}$. Since
$D_{Z}(\sigma)=D_{Y}(\sigma)=1$, there is an edge $e$ of $\sigma$ that is free
in $Y^{\prime}$ and hence in $Z^{\prime}$. Then every collapsing path
$\tau,\sigma$ in $Z$ with $e=\tau\cap\sigma$ is also a collapsing path in $Y$.
Hence $A_{Z}({\sigma,e})\subset A_{Y}({\sigma,e})$.

For the general case, assume that $D_{Y}(\sigma)=D_{Z}(\sigma)=k$. After $k$
collapses

$Z\searrow Z^{(1)}\searrow\dots\searrow Z^{(k)},\quad Y\searrow
Y^{(1)}\searrow\dots\searrow Y^{(k)},$

the $2$-simplex $\sigma$ is exposed in both $Z^{(k)}$ and $Y^{(k)}$. Thus,
$\sigma$ has a free edge $e$ in $Y^{(k)}$ (and hence in $Z^{(k)}$ as well).
Writing $Z^{\prime}=Z^{(1)}$ and $Y^{\prime}=Y^{(1)}$, by induction, we have
$\emptyset\not=A_{Z^{\prime}}({\sigma,e})\subset A_{Y^{\prime}}({\sigma,e})$
so that any collapsing path $\sigma_{1},\dots,\sigma_{k}$ from
$\sigma_{1}=\sigma^{\prime}\subset A_{Z^{\prime}}({\sigma,e})$ to
$\sigma_{k}=\sigma$ in $Z^{\prime}$ is also a collapsing path in $Y^{\prime}$.
Note in particular that every edge of $\sigma^{\prime}$ that is free in
$Z^{\prime}$ is also free in $Y^{\prime}$. Consequently, for every free
triangle $\tau$ in $Z$ which meets $\sigma^{\prime}$ in an edge free in
$Z^{\prime}$, the collapsing path
$\tau=\sigma_{0},\sigma_{1},\dots,\sigma_{k}$ in $Z$ is a collapsing path in
$Y$. The result follows. ∎

######  Corollary 11.

Let $Z\subset Y$ be 2-complexes such that for a 2-simplex $\sigma$ of $Z$ none
of the edges $e\in A_{Z}(\sigma)\subset\partial Z$ is free in $Y$. Then

$D_{Z}(\sigma)+1\leq D_{Y}(\sigma).$

###### Proof.

For a contradiction, assume that $D_{Y}(\sigma)\leq D_{Z}(\sigma)$. Then
$D_{Y}(\sigma)=D_{Z}(\sigma)$ by Lemma 5. We may now apply Lemma 10 which
claims that there is an edge $e$ of $\sigma$ for which
$\emptyset\not=A_{Z}(\sigma,e)\subset A_{Y}(\sigma,e)\subset\partial Y$. This
contradicts our assumption that no edge in $A_{Z}(\sigma)$ lies on the
boundary $\partial Y$. ∎

###  2.4 The list of forbidden $r$-pseudo-surfaces $\mathcal{L}_{k,r}$

For a pair of integers $k=0,1,\dots,$ and $r=2,3,\dots$ we denote by
$\mathcal{L}_{k,r}$ the set of all isomorphism types of $r$-pseudo-surfaces
$S$ with the following properties:

  1. (a)

Each $S\in\mathcal{L}_{k,r}$ has a specified 2-simplex $\sigma_{\ast}$ (called
the center).

  2. (b)

If $\partial S\not=\emptyset$ then $D_{S}(\sigma_{\ast})=k$.

  3. (c)

$d_{S}(\sigma_{\ast},\sigma)\leq k$ for any 2-simplex $\sigma$.

Figure 1: Surfaces $\mathcal{L}_{1,2}$.

Note that $\mathcal{L}_{0,r}=\\{S\\}$ consists of a single complex
$S=\sigma_{\ast}$ (the triangle).

The set $\mathcal{L}_{1,2}$ consists of the three surfaces shown in Figure 1.
Each of the surfaces a, b, c is a union of 4 triangles. The surface c is a
tetrahedron, b is a tetrahedron with one face open, and a is a fully flattened
tetrahedron.

It is clear that $\mathcal{L}_{k,r}$ is finite and
$\mathcal{L}_{k,r}\subset\mathcal{L}_{k,r+1}$.

######  Example 12.

Consider the following important family of surfaces
$S_{k}\in\mathcal{L}_{k,2}$ where $k=0,1,2,\dots$. The first surface $S_{0}$
is defined as a single triangle $S_{0}=\sigma_{\ast}$. The next surface
$S_{1}$ is the shown in Figure 1 a. Surfaces $S_{2}$ and $S_{3}$ are shown in
Figure 2. In general, the surface $S_{k}$ is obtained from $S_{k-1}$ by adding
a triangle to every edge of the boundary $\partial S_{k-1}$. It is clear that
for the central triangle $\sigma_{\ast}$ of $S_{k}$, one has
$D_{S_{k}}(\sigma_{\ast})=k$. Thus $S_{k}$ is not collapsible to a graph in
$k$ steps, but is collapsible in $k+1$ steps.

Figure 2: Surfaces $S_{k}\in\mathcal{L}_{k,2}$.

The following Theorem plays a key role in this paper:

######  Theorem 13.

A 2-complex $Y$ of degree at most $r\geq 2$ is not collapsible to a graph in
$k$ steps, where $k=0,1,2,\dots$, if and only if there is a surface
$S\in\mathcal{L}_{k,r}$ which admits a simplicial embedding $S\to Y$.

In the proof, we will use the following statement:

######  Lemma 14.

Let $Y$ be a finite 2-dimensional simplicial complex of degree at most $r$ and
let $\sigma$ be a 2-simplex in $Y$ with $D_{Y}(\sigma)=k$, where
$k=0,1,2,\dots$. Then there exists a surface $S\in\mathcal{L}_{k,r}$ and a
simplicial embedding $S\to Y$ such that the central simplex $\sigma_{\ast}$ of
$S$ is mapped onto $\sigma$.

###### Proof of Lemma 14.

We will use induction on $k=D_{Y}(\sigma)$. For $k=0$, the statement is
obvious. Assume that it is true for all cases with $D_{Y}(\sigma)<k$, and
consider the situation when $D_{Y}(\sigma)=k>0$. If $Y\searrow Y^{\prime}$ is
the first collapse, then $\sigma\subset Y^{\prime}$ and clearly

$D_{Y^{\prime}}(\sigma)=k-1$

and $Y^{\prime}$ has degree at most $r$. By the inductive hypothesis, there
exists $S^{\prime}\in\mathcal{L}_{k-1,r}$ and a simplicial embedding
$S^{\prime}\to Y^{\prime}$, mapping the central simplex of $S^{\prime}$ onto
$\sigma$.

For each edge $e$ lying in $A_{S^{\prime}}(\sigma)$ choose a 2-simplex
$\sigma_{e}\subset Y$ as follows. If $e\subset\partial Y^{\prime}$, let
$\sigma_{e}$ be any free triangle in $Y$ containing $e$. If
$e\not\subset\partial Y^{\prime}$, let $\sigma_{e}$ be any triangle in
$Y^{\prime}$ containing $e$ which is not in $S^{\prime}$; such $\sigma_{e}$
exists since $e\not\subset\partial Y^{\prime}$.

Next we define a subcomplex $S\subset Y$ as the union

$S=S^{\prime}\cup\bigcup_{e}\sigma_{e}\,\subset Y,$

where $e$ runs over the edges in $A_{S^{\prime}}(\sigma)$. Note that $S$ is
finite, pure, and strongly connected since $S^{\prime}$ is an $r$-pseudo-
surface. Moreover, the degree of $S$ is at most $r$ since it is a subcomplex
of $Y$. One has $D_{S}(\sigma)\geq k$ by Corollary 11. More precisely, we
obtain that $D_{S}(\sigma)=k$ by Lemma 5. Finally we observe that obviously
$d_{S}(\sigma,\sigma^{\prime})\leq k$ for any 2-simplex $\sigma^{\prime}$ of
$S$. Thus, $S\in\mathcal{L}_{k,r}$. ∎

###### Proof of Theorem 13.

Consider the sequence of successive collapses $Y\searrow Y^{(1)}\searrow
Y^{(2)}\searrow Y^{(3)}\searrow\dots$. We assume that $Y$ is not collapsible
to a graph in $k$ steps, which implies that there are two possibilities:
either (a) $Y^{(i)}\not=Y^{(i+1)}$ for any $i<k$; or (b) for some $i<k$, one
has $\partial Y^{(i)}=\emptyset$.

In case (a), the complex $Y$ contains a 2-simplex with $D_{Y}(\sigma)=k$ and
Lemma 14 gives us an embedding of an $r$-pseudo-surface
$S\in\mathcal{L}_{k,r}$ into $Y$.

In case (b), we have $\partial Y^{(i)}=\emptyset$ for some $i<k$. Fix a
2-simplex $\sigma_{\ast}\in Y^{(i)}$ and consider distances
$d_{Y^{(i)}}(\sigma_{\ast},\sigma)$ to various 2-simplexes $\sigma$ of
$Y^{(i)}$. If all these distances are less than or equal to $k$, then
$Y^{(i)}$ belongs to $\mathcal{L}_{k,r}$ and we are done. If there are
simplexes $\sigma$ such that $d_{Y^{(i)}}(\sigma_{\ast},\sigma)>k$, then
consider the subcomplex $Z\subset Y^{(i)}$ defined as the union of all
$\sigma$ with $d_{Y^{(i)}}(\sigma_{\ast},\sigma)\leq k$.

Clearly $Z$ is not collapsible to a graph in $k$ steps. Therefore, in the
sequence of collapses $Z\searrow Z^{(1)}\searrow Z^{(2)}\searrow
Z^{(3)}\searrow\dots$, we again have either case (a) or (b) as above. In case
(a), we apply Lemma 14; and in case (b), we obtain a subcomplex $S\subset Z$
with $\partial S=\emptyset$ such that $d(\sigma_{\ast},\sigma)\leq k$ for any
$\sigma\subset S$. We have $S\in\mathcal{L}_{k,r}$ in either case, completing
the proof. ∎

##  3 Collapsibility of a random 2-complex

###  3.1 The degree sequence

Recall that the degree of an edge $e$ in a 2-complex is defined as the number
of 2-simplexes which contain $e$. The degree of an edge in a random 2-complex
$Y\in G(\Delta_{n}^{(2)},p)$ is an integer in the set $\\{0,1,\dots,n-2\\}$.

Let $X_{k}:G(\Delta_{n}^{(2)},p)\to{\mathbf{Z}}$ be the random variable
counting the number of edges of degree $k$ in a random $2$-complex, where
$k=0,1,2,\dots,n-2$. A straightforward calculation reveals that

${\mathbb{E}}(X_{k})={n\choose 2}{{n-2}\choose k}p^{k}(1-p)^{n-2-k}.$

The expectation of the number of edges of degree at least $r$ in a random
$2$-complex is

$\sum_{k=r}^{n-2}{\mathbb{E}}(X_{k})\leq
n^{2}\sum_{k=r}^{n-2}(pn)^{k}\leq\frac{n^{2}(pn)^{r}}{1-pn}.$ (1)

######  Corollary 15.

The probability that a random 2-complex $Y\in G(\Delta_{n}^{(2)},p)$ has an
edge of degree at least $r$ is less than or equal to

$\frac{n^{2+r}p^{r}}{1-pn}.$

Thus, if

$p\ll n^{-1-\frac{2}{r}},$

then a random 2-complex $Y\in G(\Delta_{n}^{(2)},p)$ has no edges of degree
$r$ or greater, a.a.s.

###### Proof.

This follows from inequality (1) by applying the first moment method, see, for
instance, [JŁR00]. ∎

###  3.2 The invariant $\tilde{\mu}(S)$.

Following [BHK08] and [CFK10], for a $2$-complex $S$ with $v=v(S)$ vertices
and $f=f(S)>0$ faces one defines

$\mu(S)=\frac{v}{f}\in\mathbb{Q},$

and

$\tilde{\mu}(S)=\min_{S^{\prime}\subset S}\mu(S^{\prime}),$

where $S^{\prime}$ runs over all subcomplexes of $S$ or, equivalently, over
all pure subcomplexes $S^{\prime}\subset S$. Note the following monotonicity
property of $\tilde{\mu}$:

$\displaystyle\mbox{if}\quad S\subset
T,\quad\mbox{then}\quad\tilde{\mu}(S)\geq\tilde{\mu}(T).$ (2)

The invariant $\tilde{\mu}$ controls embeddability of finite 2-complexes into
random 2-complexes as illustrated by the following result.

######  Theorem 16 ([CFK10]).

Let $S$ be a finite simplicial complex.

  1. (a)

If $p\ll n^{-\tilde{\mu}(S)}$, the probability that $S$ admits a simplicial
embedding into a random 2-complex $Y\subset G(\Delta_{n}^{(2)},p)$ tends to
zero as $n\to\infty$;

  2. (b)

If $p\gg n^{-\tilde{\mu}(S)}$, the probability that $S$ admits a simplicial
embedding into a random 2-complex $Y\subset G(\Delta_{n}^{(2)},p)$ tends to
one as $n\to\infty$.

######  Definition 17.

A 2-complex $S$ is called balanced if $\tilde{\mu}(S)=\mu(S)$, or,
equivalently, $\mu(S^{\prime})\geq\mu(S)$ for any subcomplex
$S^{\prime}\subset S$.

Any triangulated surface is balanced, see [CFK10].

######  Example 18.

Suppose that a 2-complex $S$ has a free triangle with two free edges, and that
the result $S^{\prime}$ of removing this triangle satisfies
$\mu(S^{\prime})<1$. Then $\mu(S)>\mu(S^{\prime})$ and $S$ is unbalanced.
Indeed, if $\mu(S^{\prime})=v/f$, where $v=v(S^{\prime})$ and
$f=f(S^{\prime})$, then $v<f$ and we have $\mu(S)=(v+1)/(f+1)>v/f$. In this
way one produces many unbalance 2-complexes, including 2-disks.

Next, we examine the $\tilde{\mu}$ invariants of 2-complexes
$S\in\mathcal{L}_{k,r}$.

######  Lemma 19.

Let $S$ be a closed 2-complex, i.e., $\partial S=\emptyset$. Then
$\tilde{\mu}(S)\leq 1$.

###### Proof.

Without loss of generality, we may assume that $S$ is connected, since
otherwise we can apply the following arguments to a connected component of $S$
and use the monotonicity property (2). Moreover, we may assume that $S$ is
pure, since otherwise we may deal with the maximal pure subcomplex of $S$
instead of $S$.

Suppose first that $H_{2}(S;{\mathbf{Z}}_{2})=0$. Then by the Euler–Poincaré
theorem, $\chi(S)\leq 1$, and we have

$v-e+f=\chi(S)\leq 1,\quad\mbox{and}\quad 3f\geq 2e,$

where $v,e,f$ denote the numbers of vertices, edges and faces in $S$. In the
latter inequality we used the assumptions that $S$ is pure and closed. These
inequalities imply

$v-f/2\leq\chi(S)\leq 1,\quad\mbox{and}\quad\mu(S)\leq 1/2+1/f.$

Since $f\geq 4$ we obtain that $\tilde{\mu}(S)\leq\mu(S)\leq 3/4<1.$

Assume now that $H_{2}(S;{\mathbf{Z}}_{2})\not=0$. We will show that there is
a subcomplex $S^{\prime}\subset S$ which is also closed, $\partial
S^{\prime}=\emptyset$, and satisfies
$H_{2}(S^{\prime};{\mathbf{Z}}_{2})={\mathbf{Z}}_{2}$. Indeed, consider a
nonzero two-dimensional cycle $c=\sum_{i\in I}\sigma_{i}$ with
${\mathbf{Z}}_{2}$ coefficients, where the $\sigma_{i}$ are distinct
2-simplexes of $S$. Let $I^{\prime}\subseteq I$ be the minimal subset of the
indexing set $I$ for which $c^{\prime}=\sum_{i\in I^{\prime}}\sigma_{i}$ is
still a cycle, and let $S^{\prime}=\bigcup_{i\in I^{\prime}}\sigma_{i}$ be the
corresponding subcomplex of $S$. Then clearly
$H_{2}(S^{\prime};{\mathbf{Z}}_{2})={\mathbf{Z}}_{2}$ and $S^{\prime}$ is
closed and pure.

By the Euler–Poincaré theorem, $\chi(S^{\prime})\leq 2$, and we have

$v^{\prime}-e^{\prime}+f^{\prime}=\chi(S^{\prime})\leq 2,\quad\mbox{and}\quad
3f^{\prime}\geq 2e^{\prime},$

where $v^{\prime},e^{\prime},f^{\prime}$ denote the numbers of vertices, edges
and faces in $S^{\prime}$. This gives

$v^{\prime}-f^{\prime}/2\leq\chi(S^{\prime})\leq 2,$

and

$\displaystyle\mu(S^{\prime})\leq\frac{1}{2}+\frac{2}{f^{\prime}}.$ (3)

Since $f^{\prime}\geq 4$, the last inequality gives $\mu(S^{\prime})\leq 1$.
Finally, we have $\tilde{\mu}(S)\leq\mu(S^{\prime})\leq 1$. ∎

######  Lemma 20.

If $S\in\mathcal{L}_{k,r}$ for some $k\geq 0$, $r\geq 2$ then one has

$\displaystyle\tilde{\mu}(S)\leq 1+\frac{2}{k+1}.$ (4)

###### Proof.

If $S$ is closed the result follows from Lemma 19. Assume now that $\partial
S\not=\emptyset$. Let $\sigma_{\ast}$ be the central simplex of $S$ and let
$\sigma_{0},\sigma_{1},\dots,\sigma_{k}=\sigma_{\ast}$ be a collapsing path
leading to $\sigma_{\ast}$. Here $D_{S}(\sigma_{i})=i$ and
$\sigma_{i}\cap\sigma_{i+1}$ is an edge, see Definition 7. Then the union
$S^{\prime}=\cup_{i=0}^{k}\sigma_{i}$ is a subcomplex having exactly $k+1$
faces and at most $k+3$ vertices. Thus,

$\mu(S^{\prime})\leq\frac{k+3}{k+1}=1+\frac{2}{k+1},$

establishing (4). ∎

###  3.3 The threshold for $k$-collapsibility.

######  Definition 21.

Let $\tilde{\mu}_{k,r}$ denote the largest possible value of the invariant
$\tilde{\mu}(S)$ for $S$ a forbidden $r$-pseudo-surface,

$\tilde{\mu}_{k,r}\,=\,\max_{S\in\mathcal{L}_{k,r}}\tilde{\mu}(S)\,\in\mathbb{Q}.$

For instance, examining the surfaces shown in Figure 1 reveals that
$\tilde{\mu}_{1,2}=3/2$.

######  Theorem 22.

Consider a random 2-complex $Y\in G(\Delta_{n}^{(2)},p)$.

  1. (a)

If for some $r\geq 2$ and $k\geq 1$, one has

$p\ll n^{-1-\frac{2}{r+1}}\quad\mbox{and}\quad p\ll n^{-\tilde{\mu}_{k,r}},$

then $Y$ is collapsible to a graph in at most $k$ steps, a.a.s.

  2. (b)

If for some $r\geq 2$ and $k\geq 1$, one has $p\gg n^{-\tilde{\mu}_{k,r}}$,
then $Y$ is not collapsible to a graph in $k$ or fewer steps, a.a.s.

###### Proof.

By Corollary 15, if $p\ll n^{-1-\frac{2}{r+1}}$, then a random 2-complex $Y\in
G(\Delta_{n}^{(2)},p)$ has degree at most $r$, a.a.s. Next, we apply Theorem
13 and examine the embeddability of complexes $S\in\mathcal{L}_{k,r}$ into
$Y$. By Theorem 16 (a), if $p\ll n^{-\tilde{\mu}(S)}$, then $S$ does not embed
into $Y$, a.a.s. Since $\tilde{\mu}_{k,r}\geq\tilde{\mu}(S)$, we see that the
assumption $p\ll n^{-\tilde{\mu}_{k,r}}$ implies that no
$S\in\mathcal{L}_{k,r}$ can be embedded into $Y$, a.a.s. Thus, by Theorem 13,
we see that $Y$ is collapsible to a graph in $k$ or fewer steps. This proves
part (a).

To prove part (b), we apply Theorem 16 (b) to conclude that if $p\gg
n^{-\tilde{\mu}_{k,r}}$, then there exists $S\in\mathcal{L}_{k,r}$ which is
embeddable into $Y$, a.a.s. This implies that $Y$ is not collapsible to a
graph in at most $k$ steps, a.a.s. ∎

######  Example 23.

Consider the surface $S_{k}\in\mathcal{L}_{k,2}$ introduced in Example 12.
Note that $S_{k}\in\mathcal{L}_{k,r}$ for any $r\geq 2$. The numbers of
vertices $v_{k}$ and faces $f_{k}$ of $S_{k}$ satisfy the recurrence relations

$\displaystyle v_{k}=2\cdot v_{k-1}\quad\mbox{and}\quad
f_{k}=v_{k-1}+f_{k-1}.$ (5)

Indeed, viewing $S_{k-1}$ as a subcomplex of $S_{k}$, we see that all vertices
of $S_{k-1}$ lie on the boundary, and each edge of the boundary of $S_{k-1}$
adds a vertex to $S_{k}$. This explains the first equation. For the second,
note that the number of new triangles in $S_{k}$ is equal to the number of
edges on $\partial S_{k-1}$.

Since $v_{0}=3$ and $f_{0}=1$, solving the recurrence relations (5) yields

$v_{k}=3\cdot 2^{k}\quad\mbox{and}\quad f_{k}=3\cdot 2^{k}-2.$

Consequently,

$\mu(S_{k})=1+\frac{1}{3\cdot 2^{k-1}-1}.$

######  Lemma 24.

The surface $S_{k}$ is balanced, and hence

$\tilde{\mu}(S_{k})=\mu(S_{k})=1+\frac{1}{3\cdot 2^{k-1}-1}.$

###### Proof.

Let $S$ be a pure subcomplex of $S_{k}$ with $v=v(S)$ vertices and $f=f(S)$
faces. Write $v=v_{k}-m$ and $f=f_{k}-n$, where $v_{k}$ and $f_{k}$ are as
above and $m$ and $n$ are the number of vertices and faces which are in
$S_{k}$, but not in $S$. We claim that $m=v_{k}-v\leq f_{k}-f=n$. This
assertion is established by induction.

The case $k=0$ is trivial. So assume inductively that for any $i<k$ and
$S^{\prime}\subset S_{i}$ a pure subcomplex, we have
$v(S_{i})-v(S^{\prime})\leq f(S_{i})-f(S^{\prime})$.

For a pure subcomplex $S\subset S_{k}$ as above, let $S^{\prime}$ be the pure
part of $S\cap S_{k-1}$. Then, $m=m^{\prime}+m^{\prime\prime}$ and
$n=n^{\prime}+n^{\prime\prime}$, where $v(S^{\prime})=v_{k-1}-m^{\prime}$,
$f(S^{\prime})=f_{k-1}-n^{\prime}$, $m^{\prime\prime}$ is the number of
vertices in $S_{k}\smallsetminus S_{k-1}$ which are not in $S$, and
$n^{\prime\prime}$ is the number of faces in $S_{k}\smallsetminus S_{k-1}$
which are not in $S$.

We have $m^{\prime}\leq n^{\prime}$ by induction. Observe that the vertices of
$S_{k}\smallsetminus S_{k-1}$ are in one-to-one correspondence with the faces
of $S_{k}\smallsetminus S_{k-1}$. If such a vertex is not in $S$, then the
corresponding face cannot be in $S$ either. Consequently,
$m^{\prime\prime}=n^{\prime\prime}$, and $m=m^{\prime}+m^{\prime\prime}\leq
n^{\prime}+n^{\prime\prime}=n$, completing the proof of the claim.

It follows immediately that $\mu(S)\geq\mu(S_{k})=\mu_{k}$. Indeed,

$\frac{v}{f}-\frac{v_{k}}{f_{k}}=\frac{v_{k}-m}{f_{k}-n}-\frac{v_{k}}{f_{k}}=\frac{nv_{k}-mf_{k}}{f_{k}(f_{k}-n)}=\frac{\mu_{k}n-m}{f_{k}-n}\geq\frac{n-m}{f_{k}-n}\geq
0.$

Thus, $S_{k}$ is balanced. ∎

From Lemmas 20 and 24 we obtain:

######  Corollary 25.

For any $r\geq 2$ and $k\geq 0$, one has the following inequalities:

$1+\frac{1}{3\cdot
2^{k-1}-1}\,\leq\,\tilde{\mu}_{k,r}\,\leq\,1+\frac{2}{k+1}.$

Note that the obtained upper and lower bounds for $\tilde{\mu}_{k,r}$ are
independent of $r$.

We believe that $\tilde{\mu}_{k,r}=1+1/(3\cdot 2^{k-1}-1)$.

###### Proof of Theorem 1.

The main theorem is now an immediate consequence of Theorem 22 and Corollary
25:

(a) Assume that $p\ll n^{-1-2/(k+1)}$ for some $k\geq 1$. According to
Corollary 25, $\tilde{\mu}_{k,r}\leq 1+2/(k+1).$ Choosing $r=\mbox{max}(2,k)$,
it then follows from Theorem 22 (a) that $Y\in G(\Delta_{n}^{(2)},p)$ is
collapsible to a graph in at most $k$ steps, a.a.s.

(b) Assume that $p\gg n^{-1-1/(3\cdot 2^{k-1}-1)}$ for some $k\geq 1$. Then by
Theorem 16 and Lemma 24 the surface $S_{k}$ (see Example 12) embeds into $Y$,
a.a.s. Since $S_{k}$ cannot be collapsed to a graph in $k$ or fewer steps we
obtain that $Y$ is not collapsible to a graph in $k$ or fewer steps. ∎

## References

  * [AS00] N. Alon, J. Spencer, The Probabilistic Method, Third edition, Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley & Sons, Inc., Hoboken, NJ, 2008. MR2437651
  * [BHK08] E. Babson, C. Hoffman, M. Kahle, The fundamental group of random $2$-complexes, preprint 2008. arXiv:0711.2704
  * [Bol08] B. Bollobás, Random Graphs, Second edition, Cambridge University Press, 2008. Cambridge Stud. Adv. Math., 73, Cambridge, 2001. MR1864966
  * [CFK10] A. Costa, M. Farber, T. Kappeler, Topology of random 2-complexes, preprint 2010.
  * [ER60] P. Erdős, A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 17–61. MR0125031
  * [HMS93] C. Hog-Angeloni, W. Metzler, A. Sieradski, Two-dimensional homotopy and combinatorial group theory, London Math. Soc. Lecture Note Ser., 197, Cambridge University Press, Cambridge, 1993. MR1279174
  * [JŁR00] S. Janson, T. Łuczak, A. Ruciński, Random graphs, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley-Interscience, New York, 2000. MR1782847
  * [Koz09] D. Kozlov, The threshold function for vanishing of the top homology group of random $d$-complexes, preprint 2009.
arXiv:0904.1652.

  * [LM06] N. Linial, R. Meshulam, Homological connectivity of random $2$-complexes, Combinatorica 26 (2006), 475–487. MR2260850
  * [MW09] R. Meshulam, N. Wallach, Homological connectivity of random $k$-complexes, Random Structures & Algorithms 34 (2009), 408–417. MR2504405

Daniel C. Cohen

Department of Mathematics

Louisiana State University

Baton Rouge, LA 70803 USA

<EMAIL_ADDRESS>
www.math.lsu.edu/$\sim$cohen

Michael Farber

Department of Mathematical Sciences

Durham University

Durham, DH1 3LE, UK

<EMAIL_ADDRESS>
http://maths.dur.ac.uk/$\sim$dma0mf/

Thomas Kappeler

Mathematical Insitutte

University of Zurich

Winterthurerstrasse 190, CH-8057

Zurich, Switzerland

<EMAIL_ADDRESS>