On the phase transition in random simplicial complexes

Nathan Linial¹ ; Yuval Peled¹

¹ Department of Computer Science, Hebrew University, Jerusalem, Israel

Annals of mathematics, Tome 184 (2016) no. 3, pp. 745-773.

Résumé

It is well known that the $G(n,p)$ model of random graphs undergoes a dramatic change around $p=\frac 1n$. It is here that the random graph, almost surely, contains cycles, and here it first acquires a giant (i.e., order $\Omega(n)$) connected component. Several years ago, Linial and Meshulam 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)$. We also compute the real Betti numbers 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\ge 2$ the emergence of the giant shadow is a first order phase transition.

Détail

DOI : 10.4007/annals.2016.184.3.3