×
Linial, Nathan; Peled, Yuval

On the phase transition in random simplicial complexes. (English) Zbl 1348.05193

Ann. Math. (2) 184, No. 3, 745-773 (2016).
Summary: It is well known that the \(G(n,p)\) model of random graphs undergoes a dramatic change around \(p=\frac{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, N. Linial and R. Meshulam [Combinatorica 26, No. 4, 475–487 (2006; Zbl 1121.55013)] 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\geq 2\) the emergence of the giant shadow is a first order phase transition.

Cited in 2 Reviews
Cited in 22 Documents

MSC:

05C80 Random graphs (graph-theoretic aspects)
05E45 Combinatorial aspects of simplicial complexes
60C05 Combinatorial probability

Keywords:

high-dimensional combinatorics; homology; local weak convergence; phase transition; probabilistic topology; shadow of simplicial complexes; simplicial complexes; spectral measure

Citations:

Zbl 1121.55013
PDF BibTeX XML Cite
\textit{N. Linial} and \textit{Y. Peled}, Ann. Math. (2) 184, No. 3, 745--773 (2016; Zbl 1348.05193)
Full Text: DOI arXiv
  • logo of hbz
  • logo of WorldCat

References:

[1] D. Aldous, ”The \(\zeta(2)\) limit in the random assignment problem,” Random Structures Algorithms, vol. 18, iss. 4, pp. 381-418, 2001. · Zbl 0993.60018
[2] D. Aldous and R. Lyons, ”Processes on unimodular random networks,” Electron. J. Probab., vol. 12, p. no. 54, 1454-1508, 2007. · Zbl 1131.60003
[3] D. Aldous and M. J. Steele, ”The objective method: probabilistic combinatorial optimization and local weak convergence,” in Probability on Discrete Structures, New York: Springer-Verlag, 2004, vol. 110, pp. 1-72. · Zbl 1037.60008
[4] L. Aronshtam and N. Linial, ”The threshold for \(d\)-collapsibility in random complexes,” Random Structures Algorithms, vol. 48, pp. 260-269, 2016. · Zbl 1332.05158
[5] L. Aronshtam and N. Linial, ”When does the top homology of a random simplicial complex vanish?,” Random Structures & Algorithms, vol. 46, pp. 26-35, 2015. · Zbl 1326.55019
[6] L. Aronshtam, N. Linial, T. Łuczak, and R. Meshulam, ”Collapsibility and vanishing of top homology in random simplicial complexes,” Discrete Comput. Geom., vol. 49, iss. 2, pp. 317-334, 2013. · Zbl 1260.05171
[7] E. Babson, C. Hoffman, and M. Kahle, ”The fundamental group of random 2-complexes,” J. Amer. Math. Soc., vol. 24, iss. 1, pp. 1-28, 2011. · Zbl 1270.20042
[8] I. Benjamini and O. Schramm, ”Recurrence of distributional limits of finite planar graphs,” in Selected Works of Oded Schramm. Volume 1, 2, New York: Springer-Verlag, 2011, pp. 533-545. · Zbl 1248.01043
[9] C. Bordenave and M. Lelarge, ”Resolvent of large random graphs,” Random Structures Algorithms, vol. 37, iss. 3, pp. 332-352, 2010. · Zbl 1209.05222
[10] C. Bordenave, M. Lelarge, and J. Salez, ”The rank of diluted random graphs,” Ann. Probab., vol. 39, iss. 3, pp. 1097-1121, 2011. · Zbl 1298.05283
[11] A. Dembo and A. Montanari, ”Gibbs measures and phase transitions on sparse random graphs,” Braz. J. Probab. Stat., vol. 24, iss. 2, pp. 137-211, 2010. · Zbl 1205.05209
[12] M. Dietzfelbinger, M. Goerdt, M. Mitzenmacher, M. Montanari, R. Pagh, and M. Rink, ”Tight thresholds for cuckoo hashing via XORSAT,” in Automata, Languages and Programming, New York: Springer-Verlag, 2010, pp. 213-225. · Zbl 1256.68047
[13] G. R. Grimmett, ”Random labelled trees and their branching networks,” J. Austral. Math. Soc. Ser. A, vol. 30, iss. 2, pp. 229-237, 1980/81. · Zbl 0455.05028
[14] C. Hoffman, M. Kahle, and E. Paquette, The threshold for integer homology in random \(d\)-complexes, 2013. · Zbl 1365.05261
[15] S. Janson, D. E. Knuth, T. Łuczak, and B. Pittel, ”The birth of the giant component,” Random Structures Algorithms, vol. 4, iss. 3, pp. 231-358, 1993. · Zbl 0795.05127
[16] S. Janson, T. Łuczak, and A. Rucinski, Random Graphs, New York: Wiley-Interscience, 2000. · Zbl 0968.05003
[17] G. Kalai, ”Enumeration of \({\mathbf Q}\)-acyclic simplicial complexes,” Israel J. Math., vol. 45, iss. 4, pp. 337-351, 1983. · Zbl 0535.57011
[18] J. H. Kim, ”Poisson cloning model for random graphs,” in International Congress of Mathematicians. Vol. III, Zürich: Eur. Math. Soc., 2006, pp. 873-897. · Zbl 1100.05093
[19] M. Lelarge, ”A new approach to the orientation of random hypergraphs,” in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, New York, 2012, pp. 251-264.
[20] N. Linial and R. Meshulam, ”Homological connectivity of random 2-complexes,” Combinatorica, vol. 26, iss. 4, pp. 475-487, 2006. · Zbl 1121.55013
[21] N. Linial, I. Newman, Y. Peled, and Y. Rabinovich, Extremal problems on shadows and hypercuts in simplicial complexes, 2014.
[22] R. Lyons, ”Asymptotic enumeration of spanning trees,” Combin. Probab. Comput., vol. 14, iss. 4, pp. 491-522, 2005. · Zbl 1076.05007
[23] C. McDiarmid, ”On the method of bounded differences,” in Surveys in Combinatorics, 1989, Cambridge: Cambridge Univ. Press, 1989, vol. 141, pp. 148-188. · Zbl 0712.05012
[24] R. Meshulam and N. Wallach, ”Homological connectivity of random \(k\)-dimensional complexes,” Random Structures Algorithms, vol. 34, iss. 3, pp. 408-417, 2009. · Zbl 1177.55011
[25] B. Mohar, ”The spectrum of an infinite graph,” Linear Algebra Appl., vol. 48, pp. 245-256, 1982. · Zbl 0502.05040
[26] M. Molloy, ”Cores in random hypergraphs and Boolean formulas,” Random Structures Algorithms, vol. 27, iss. 1, pp. 124-135, 2005. · Zbl 1068.05063
[27] B. Pittel and G. B. Sorkin, ”The satisfiability threshold for \(k\)-XORSAT,” Combin. Probab. Comput., vol. 25, iss. 2, pp. 236-268, 2016. · Zbl 1372.68193
[28] M. Reed and B. Simon, Methods of Modern Mathematical Physics. I: Functional Analysis, Second ed., New York: Academic Press [Harcourt Brace Jovanovich, Publishers], 1980. · Zbl 0459.46001
[29] J. Salez, Some implications of local weak convergence for large random graphs, 2011.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.