On the phase transition in random simplicial complexes

By N. Linial, Yuval Peled. 2014

80 citations recorded by the source corpus.

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 is, almost surely, no longer a forest, and here it first acquires a giant (i.e., order $\Omega(n)$) connected component. Several years ago, Linial and Meshulam have introduced the $X_d(n,p)$ model, a probability space of $n$-vertex $d$-dimensional simplicial complexes, where $X_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 $X_d(n,p)$. We also compute the real Betti numbers of $X_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.

Subfields: Computational Theory and Mathematics, Statistics and Probability, Signal Processing

View Paper: https://www.semanticscholar.org/paper/77cbee6339336da3206cd97fa572f8878c9e4cf4

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Statistics and Probability

In Signal Processing

Citations in the corpus

Spectral Gaps of Random Graphs and Applications (2012, methodology): “This is the same point as the homological phase transition studied by Linial and Peled [36].”