random topology

////////////////////////////////////////////

Let $Y \sim Y_d(n,p)$ denote the Bernoulli random $d$-dimensional simplicial complex. We answer a question of Linial and Meshulam from 2003, showing that the threshold for vanishing of homology $H_{d-1}(Y; \mathbb{Z})$ is less than $80d \log n / n$. This bound is tight, up to a constant factor.

This expository article is based on a lecture from the Stanford Symposium on Algebraic Topology: Application and New Directions, held in honor of Gunnar Carlsson, Ralph Cohen, and Ib Madsen.

In a seminal paper, Erdős and Rényi identified the threshold for connectivity of the random graph $G(n,p)$. In particular, they showed that if $p \gg \log n / n$ then $G(n,p)$ is almost always connected, and if $p \ll \log n /n$ then $G(n,p)$ is almost always disconnected, as $n \to \infty$. The clique complex $X(H)$ of a graph $H$ is the simplicial complex with all complete subgraphs of $H$ as its faces. In contrast to the zeroth homology group of $X(H)$, which measures the number of connected components of $H$, the higher dimensional homology groups of $X(H)$ do not correspond to monotone graph properties. There are nevertheless higher dimensional analogues of the Erdős–Rényi Theorem. We study here the higher homology groups of $X(G(n,p))$. For $k > 0$ we show the following. If $p = n^{\alpha}$, with $\alpha < -1/k$ or $\alpha > - 1/(2k+1)$, then the $k$th homology group of $X(G(n,p))$ is almost always vanishing, and if $-1/k < \alpha < -1/(k+1)$, then it is almost always nonvanishing. We also give estimates for the expected rank of homology, and exhibit explicit nontrivial classes in the nonvanishing regime. These estimates suggest that almost all d-dimensional clique complexes have only one nonvanishing dimension of homology, and we cannot rule out the possibility that they are homotopy equivalent to wedges of spheres.

We study Linial-Meshulam random $2$-complexes, which are two-dimensional analogues of Erdős–Rényi random graphs. We find the threshold for simple connectivity to be roughly $p = n^{-1/2}$. (The exponent is sharp.) This is in contrast to the threshold for vanishing of the first homology group, which was shown earlier by Linial and Meshulam to be $p = 2 \log(n)/n$. We use a variant of Gromov's local-to-global theorem for linear isoperimetric inequalities to show that when $p = O(n^{-1/2 -\epsilon})$ the fundamental group is word hyperbolic. Along the way we classify the homotopy types of sparse $2$-dimensional simplicial complexes and establish isoperimetric inequalities for such complexes. These intermediate results do not involve randomness and may be of independent interest.

We study the expected topological properties of Cech and Vietoris-Rips complexes built on i.i.d. random points in $\mathbb{R}^d$. We find higher dimensional analogues of known results for connectivity and component counts for random geometric graphs. However, higher homology $H_k$ is not monotone when $k > 0$. In particular for every $k > 0$ we exhibit two thresholds, one where homology passes from vanishing to nonvanishing, and another where it passes back to vanishing. We give asymptotic formulas for the expectation of the Betti numbers in the sparser regimes, and bounds in the denser regimes. The main technical contribution of the article is in the application of discrete Morse theory in geometric probability.