Paper

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

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.

We exhibit a sharp threshold for vanishing of rational cohomology in random flag complexes, providing a generalization of the Erdős–Rényi theorem. As a corollary, almost all $d$-dimensional flag complexes have nontrivial (rational, reduced) homology only in middle degree $\lfloor d/2 \rfloor$.

We study $(n,k)$-scatters, which are regular $n$-gon tiles arranged so that each tile shares edges with at least $k$ others. To measure how much freedom there is in arranging scatters, we ask which shapes are unavoidable. It turns out that for a few choices of $(n,k)$ there are infinite unavoidable shapes, but otherwise they are finite. We discuss the infinite case as an analogue of crystallization. The main result here is that besides the trivial situations when there’s a unique scatter, there are only four instances of this. Scatters crystallize nontrivially just when $(n, k) = (5, 3)$, $(7, 3)$, $(10, 4)$, or $(14, 4)$.

An old theorem of Alexander Soifer's is the following: Given five points in a triangle of unit area, there must exist some three of them which form a triangle of area $1/4$ or less. It is easy to check that this is not true if "five" is replaced by "four", but can the theorem be improved in any other way? We discuss in this article two different extensions of the original result. First, we allow the value of "small", $1/4$, to vary. In particular, our main result is to show that given five points in a triangle of unit area, then there must exist some three of them determining a triangle of area $6/25$ or less. Second, we put bounds on the minimum number of small triangles determined by $n$ points in a triangle, and make a conjecture about the asymptotic right answer as $n \to \infty$. [NOTE: Conjecture 2.6 fails --- the optimal value is $3 - 2 \sqrt{2}$ not $1/6$.]

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 describe a natural topological generalization of edge expansion for graphs to regular CW complexes and prove that this property holds with high probability for certain random complexes.

For a graph $G$, the neighborhood complex $N[G]$ is the simplicial complex having all subsets of vertices with a common neighbor as its faces. It is a well known result of Lovász that if $N[G]$ is $k$-connected, then the chromatic number of $\chi(G) \ge k+3$. We prove that the connectivity of the neighborhood complex of a random graph is tightly concentrated, almost always between $1/2$ and $2/3$ of the expected clique number. We also show that the number of dimensions of nontrivial homology is almost always small, $O(\log d)$, compared to the expected dimension $d$ of the complex itself.

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 configuration spaces of hard spheres in a bounded region. We develop a general Morse-theoretic framework, and show that mechanically balanced configurations play the role of critical points. As an application, we find the precise threshold radius for a configuration space to be homotopy equivalent to the configuration space of points.