On the phase transition in random simplicial complexes

• 成果类型: Article
• 署名作者: Linial, Nathan; Peled, Yuval
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2016.184.3.3
• 发表日期: 2016
• 页码: 745-773
• 关键词: Random graphs; homological connectivity; random 2-complexes; top homology; enumeration; xorsat

摘要

It is well known that the G(n,p) model of random graphs undergoes a dramatic change around p = 1/n 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 Yd(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.