On the phase transition in random simplicial complexes

2014/10/06 by Linial, Nathan, Peled, Yuval · 6 citations
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1410.1281

Abstract

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 Ω(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₁(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≥ 2 the emergence of the giant shadow is a first order phase transition.

Cited by

• Disks, Surfaces, and Entanglement Percolation
• The persistent homology of the Linial-Meshulam process
• Cocycle stability in permutations of random simplicial complexes
• Using dense graph limit theory to count cocycles of random simplicial complexes
• Deterministic simplicial complexes
• Cycle-Consistent Helmholtz Machine: Goal-Seeded Simulation via Inverted Inference

Related

• Random simplicial complexes - around the phase transition
• When does the top homology of a random simplicial complex vanish?
• Phase transition in cohomology groups of non-uniform random simplicial\n complexes
• Soft random simplicial complexes
• Large Random Simplicial Complexes, III; The Critical Dimension