The phase transition in random simplicial complexes

-
Yuval Peled, Courant
Fine Hall 214

The $G(n,p)$ model of random graphs undergoes a dramatic change around $p=1/n$. It is here that the random graph is, almost surely, no longer a forest, and here it first acquires a giant connected component. Several years ago, Linial and Meshulam have introduced the $Y_d(n,p)$ model, a probability space of $n$-vertex $d$-dimensional simplicial complexes, where $Y_1(n,p)$ coincides with $G(n,p)$. Within this model we prove a natural $d$-dimensional analog of these graph theoretic phenomena. Specifically, we determine the exact threshold for the nonvanishing of the real $d$-th homology of complexes from $Y_d(n,p)$, and show that it is strictly greater than the threshold of $d$-collapsibility. In addition, we compute the real Betti numbers, i.e. the dimension of the homology groups, of $Y_d(n,p)$ for $p=c/n$. Finally, we establish the emergence of giant shadow at this threshold. (For $d=1$ a giant shadow and a giant component are equivalent). Unlike the case for graphs, for $d > 1$  the emergence of the giant shadow is a first order phase transition. Joint work with Nati Linial.