Preprint

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

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.

We prove sharper versions of theorems of Linial--Meshulam and Meshulam--Wallach which describe the behavior for $(\mathbb{Z}/2)$-cohomology of a random $k$-dimensional simplicial complex within a narrow transition window. In particular, we show that within this window the Betti number $\beta^{k-1}$ is in the limit Poisson distributed. For $k=2$ we also prove that in an accompanying growth process, with high probability, first cohomology vanishes exactly at the moment when the last isolated $(k-1)$-simplex gets covered by a $k$-simplex.

Given a Bernoulli random graph $G \sim G(n,p)$, we determine various facts about the cohomology of graph products of groups for the graph $G$. In particular, the random graph product of a sequence of finite groups is a rational duality group with probability tending to $1$ as $n \to \infty$. This includes random right angled Coxeter groups as a special case.

We construct arbitrarily sparse locally-jammed packings of non- overlapping congruent disks in various finite area regions — in particular, we give constructions for the square, hexagon, and for certain flat tori.

We study the spectral gap of the Erdős–Rényi random graph through the connectivity threshold. In particular, we show that for any fixed $\delta > 0$, if $$p \ge \frac{(1/2 + \delta) \log n}{n},$$ then the normalized graph Laplacian of an \ER graph has all of its nonzero eigenvalues tightly concentrated around $1$. This is a strong expander property. We estimate both the decay rate of the spectral gap to $1$ and the failure probability, up to a constant factor. We also show that the $1/2$ in the above is optimal, and that if $p = \frac{c \log n}{n}$ for $c < 1/2,$ then there are eigenvalues of the Laplacian restricted to the giant component that are separated from $1.$ We then describe several applications of our spectral gap results to stochastic topology and geometric group theory. These all depend on Garland's method \cite{Garland}, a kind of spectral geometry for simplicial complexes. The following can all be considered to be higher-dimensional expander properties. First, we exhibit a sharp threshold for the fundamental group of the Bernoulli random $2$-complex to have Kazhdan's property (T). We also obtain slightly more information and can describe the large-scale structure of the group just before the (T) threshold. In this regime, the random fundamental group is with high probability the free product of a (T) group with a free group, where the free group has one generator for every isolated edge. The (T) group plays a role analogous to that of a ``giant component'' in percolation theory. Next, we give a new, short, self-contained proof of the Linial--Meshulam--Wallach theorem \cite{LM06,MW09}, identifying the cohomology-vanishing threshold of Bernoulli random $d$-complexes. Since we use spectral techniques, it only holds for $\Q$ or $\R$ coefficients rather than finite field coefficients, as in \cite{LM06} and \cite{MW09}. But it is sharp from a probabilistic point of view, providing for example, hitting time type results and limiting Poisson distributions inside the critical window. It is also a new method of proof, circumventing the combinatorial complications of cocycle counting. Similarly, results in an earlier preprint version of this article were already applied in \cite{flag} to obtain sharp cohomology-vanishing thresholds in every dimension for the random flag complex model.

A graph homomorphism from the rooted $d$-branching tree $\phi: T^d \to H$ is said to be cold if the values of $\phi$ for vertices arbitrarily far away from the root can restrict the value of $\phi$ at the root. Warmth is a graph parameter that measures the non-existence of cold maps. We study warmth of random graphs $G(n,p)$, and for every $d \ge 1$, we exhibit a nearly-sharp threshold for the existence of cold maps. As a corollary, for $p=O(n^{-\alpha})$ warmth of $G(n,p)$ is concentrated on at most two values. As another corollary, a conjecture of Lovász relating mobility to chromatic number holds for ``almost all'' graphs. Finally, our results suggest new conjectures relating graph parameters from statistical physics with graph parameters from equivariant topology.

There have been several recent articles studying homology of various types of random simplicial complexes. Some theorems have concerned thresholds for vanishing of homology, and in others estimates for the expectations of the Betti numbers. However little seems known so far about limiting distributions. In this article we establish Poisson and normal approximation theorems for Betti numbers of different kinds of random simplicial complex: Erdos-Renyi random clique complexes, random Vietoris-Rips complexes, and random Cech complexes. These results may be of practical interest in topological data analysis.

We explore the topology of configuration spaces of hard disks experimentally, and show that several changes in the topology can already be observed with a small number of particles. The results illustrate a theorem of Baryshnikov, Bubenik, and Kahle that critical points correspond to configurations of disks with balanced mechanical stresses, and suggest conjectures about the asymptotic topology as the number of disks tends to infinity.

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.