random graphs

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

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$.

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.

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.