On the phase transition in random simplicial complexes

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, 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.

  • [ald_zeta] Go to document D. Aldous, "The $\zeta(2)$ limit in the random assignment problem," Random Structures Algorithms, vol. 18, iss. 4, pp. 381-418, 2001.
    @article {ald_zeta, MRKEY = {1839499},
      AUTHOR = {Aldous, David},
      TITLE = {The {$\zeta(2)$} limit in the random assignment problem},
      JOURNAL = {Random Structures Algorithms},
      FJOURNAL = {Random Structures \& Algorithms},
      VOLUME = {18},
      YEAR = {2001},
      NUMBER = {4},
      PAGES = {381--418},
      ISSN = {1042-9832},
      MRCLASS = {60C05 (60F05)},
      MRNUMBER = {1839499},
      MRREVIEWER = {Aart J. Stam},
      DOI = {10.1002/rsa.1015},
      zblnumber={0993.60018},
      }
  • [ald_lyo] Go to document D. Aldous and R. Lyons, "Processes on unimodular random networks," Electron. J. Probab., vol. 12, p. no. 54, 1454-1508, 2007.
    @article {ald_lyo, MRKEY = {2354165},
      AUTHOR = {Aldous, David and Lyons, Russell},
      TITLE = {Processes on unimodular random networks},
      JOURNAL = {Electron. J. Probab.},
      FJOURNAL = {Electronic Journal of Probability},
      VOLUME = {12},
      YEAR = {2007},
      PAGES = {no. 54, 1454--1508},
      ISSN = {1083-6489},
      MRCLASS = {60C05 (05C80 60G50)},
      MRNUMBER = {2354165},
      MRREVIEWER = {Jean-Fran{ç}ois Delmas},
      DOI = {10.1214/EJP.v12-463},
      zblnumber={1131.60003},
      }
  • [ald_ste] Go to document 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.
    @incollection {ald_ste, MRKEY = {2023650},
      AUTHOR = {Aldous, David and Steele, J. Michael},
      TITLE = {The objective method: probabilistic combinatorial optimization and local weak convergence},
      BOOKTITLE = {Probability on Discrete Structures},
      SERIES = {Encyclopaedia Math. Sci.},
      VOLUME = {110},
      PAGES = {1--72},
      PUBLISHER = {Springer-Verlag},
      YEAR = {2004},
      MRCLASS = {60C05 (05C80 60F05)},
      MRNUMBER = {2023650},
      MRREVIEWER = {Ralph Neininger},
      DOI = {10.1007/978-3-662-09444-0_1},
      ADDRESS = {New York},
      zblnumber={1037.60008},
      }
  • [col2] Go to document L. Aronshtam and N. Linial, "The threshold for $d$-collapsibility in random complexes," Random Structures Algorithms, vol. 48, pp. 260-269, 2016.
    @article{col2,
      author={Aronshtam, Lior and Linial, Nathan},
      title = {The threshold for $d$-collapsibility in random complexes},
      journal = {Random Structures Algorithms},
      fjournal = {Random Structures \& Algorithms},
      volume = {48},
      issue = {2},
      pages = {260--269},
      year = {2016},
      doi = {10.1002/rsa.20585},
      MRNUMBER = {3449598},
      ZBLNUMBER = {1332.05158},
     }
  • [acyc] Go to document 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.
    @article{acyc, MRKEY={3291292},
      AUTHOR={Aronshtam, Lior and Linial, Nathan},
      TITLE={When does the top homology of a random simplicial complex vanish?},
      JOURNAL={Random Structures \& Algorithms},
      YEAR={2015},
      VOLUME={46},
      PAGES = {26--35},
      mrnumber = {3291292},
      zblnumber = {1326.55019},
      doi = {10.1002/rsa.20495},
     }
  • [col1] Go to document 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.
    @article {col1, MRKEY = {3017914},
      AUTHOR = {Aronshtam, Lior and Linial, Nathan and {\L}uczak, Tomasz and Meshulam, Roy},
      TITLE = {Collapsibility and vanishing of top homology in random simplicial complexes},
      JOURNAL = {Discrete Comput. Geom.},
      FJOURNAL = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
      VOLUME = {49},
      YEAR = {2013},
      NUMBER = {2},
      PAGES = {317--334},
      ISSN = {0179-5376},
      CODEN = {DCGEER},
      MRCLASS = {55U10 (05C80 60D05)},
      MRNUMBER = {3017914},
      MRREVIEWER = {Michael S. Farber},
      DOI = {10.1007/s00454-012-9483-8},
      zblnumber={1260.05171},
      }
  • [BHK] Go to document 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.
    @article {BHK, MRKEY = {2726597},
      AUTHOR = {Babson, Eric and Hoffman, Christopher and Kahle, Matthew},
      TITLE = {The fundamental group of random 2-complexes},
      JOURNAL = {J. Amer. Math. Soc.},
      FJOURNAL = {Journal of the American Mathematical Society},
      VOLUME = {24},
      YEAR = {2011},
      NUMBER = {1},
      PAGES = {1--28},
      ISSN = {0894-0347},
      MRCLASS = {20F65 (05C80 05E45)},
      MRNUMBER = {2726597},
      MRREVIEWER = {Tatiana Smirnova-Nagnibeda},
      DOI = {10.1090/S0894-0347-2010-00677-7},
      zblnumber={1270.20042},
      }
  • [ben_sch] Go to document 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.
    @incollection {ben_sch, MRKEY = {2883381},
      AUTHOR = {Benjamini, Itai and Schramm, Oded},
      TITLE = {Recurrence of distributional limits of finite planar graphs},
      BOOKTITLE = {Selected Works of {O}ded {S}chramm. {V}olume 1, 2},
      SERIES = {Sel. Works Probab. Stat.},
      PAGES = {533--545},
      PUBLISHER = {Springer-Verlag},
      YEAR = {2011},
      MRCLASS = {82B41 (05C80 52C26 60G50)},
      MRNUMBER = {2883381},
      DOI = {10.1007/978-1-4419-9675-6_15},
      ADDRESS = {New York},
      zblnumber={1248.01043},
      }
  • [resolvent] Go to document C. Bordenave and M. Lelarge, "Resolvent of large random graphs," Random Structures Algorithms, vol. 37, iss. 3, pp. 332-352, 2010.
    @article {resolvent, MRKEY = {2724665},
      AUTHOR = {Bordenave, Charles and Lelarge, Marc},
      TITLE = {Resolvent of large random graphs},
      JOURNAL = {Random Structures Algorithms},
      FJOURNAL = {Random Structures \& Algorithms},
      VOLUME = {37},
      YEAR = {2010},
      NUMBER = {3},
      PAGES = {332--352},
      ISSN = {1042-9832},
      MRCLASS = {60F99 (05C80 60B20 60J80)},
      MRNUMBER = {2724665},
      DOI = {10.1002/rsa.20313},
      zblnumber={1209.05222},
      }
  • [diluted] Go to document C. Bordenave, M. Lelarge, and J. Salez, "The rank of diluted random graphs," Ann. Probab., vol. 39, iss. 3, pp. 1097-1121, 2011.
    @article {diluted, MRKEY = {2789584},
      AUTHOR = {Bordenave, Charles and Lelarge, Marc and Salez, Justin},
      TITLE = {The rank of diluted random graphs},
      JOURNAL = {Ann. Probab.},
      FJOURNAL = {The Annals of Probability},
      VOLUME = {39},
      YEAR = {2011},
      NUMBER = {3},
      PAGES = {1097--1121},
      ISSN = {0091-1798},
      CODEN = {APBYAE},
      MRCLASS = {05C80 (05C50 15B52 47A10 60B20)},
      MRNUMBER = {2789584},
      MRREVIEWER = {Marianna Bolla},
      DOI = {10.1214/10-AOP567},
      zblnumber={1298.05283},
      }
  • [dembo] Go to document 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.
    @article {dembo, MRKEY = {2643563},
      AUTHOR = {Dembo, Amir and Montanari, Andrea},
      TITLE = {Gibbs measures and phase transitions on sparse random graphs},
      JOURNAL = {Braz. J. Probab. Stat.},
      FJOURNAL = {Brazilian Journal of Probability and Statistics},
      VOLUME = {24},
      YEAR = {2010},
      NUMBER = {2},
      PAGES = {137--211},
      ISSN = {0103-0752},
      MRCLASS = {60K35 (05C80 82B26 82B44)},
      MRNUMBER = {2643563},
      MRREVIEWER = {David J. Aldous},
      DOI = {10.1214/09-BJPS027},
      zblnumber={1205.05209},
      }
  • [dietzfelbinger] Go to document 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.
    @incollection{dietzfelbinger,
      author={Dietzfelbinger, Martin and Goerdt, Martin and Mitzenmacher, Martin and Montanari, Martin and Pagh, Rasmus and Rink, Michael},
      TITLE={Tight thresholds for cuckoo hashing via {XORSAT}},
      BOOKTITLE={Automata, Languages and Programming},
      PAGES={213--225},
      PUBLISHER={Springer-Verlag},
      ADDRESS={New York},
      YEAR={2010},
      zblnumber={1256.68047},
      doi = {10.1007/978-3-642-14165-2_19},
     }
  • [grimmettLemma] Go to document 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.
    @article {grimmettLemma, MRKEY = {0607933},
      AUTHOR = {Grimmett, G. R.},
      TITLE = {Random labelled trees and their branching networks},
      JOURNAL = {J. Austral. Math. Soc. Ser. A},
      FJOURNAL = {Australian Mathematical Society. Journal. Series A},
      VOLUME = {30},
      YEAR = {1980/81},
      NUMBER = {2},
      PAGES = {229--237},
      ISSN = {0263-6115},
      MRCLASS = {05C05 (60J50)},
      MRNUMBER = {0607933},
      zblnumber={0455.05028},
      doi={10.1017/S1446788700016517},
      }
  • [HKP] C. Hoffman, M. Kahle, and E. Paquette, The threshold for integer homology in random $d$-complexes, 2013.
    @misc{HKP,
      author={Hoffman, Christopher and Kahle, Matthew and Paquette, Elliot},
      TITLE={The threshold for integer homology in random $d$-complexes},
      ARXIV={1308.6232},
      YEAR={2013},
      }
  • [birth] Go to document 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.
    @article {birth, MRKEY = {1220220},
      AUTHOR = {Janson, Svante and Knuth, Donald E. and {\L}uczak, Tomasz and Pittel, Boris},
      TITLE = {The birth of the giant component},
      JOURNAL = {Random Structures Algorithms},
      FJOURNAL = {Random Structures \& Algorithms},
      VOLUME = {4},
      YEAR = {1993},
      NUMBER = {3},
      PAGES = {231--358},
      ISSN = {1042-9832},
      MRCLASS = {05C80 (60C05)},
      MRNUMBER = {1220220},
      MRREVIEWER = {Alan M. Frieze},
      DOI = {10.1002/rsa.3240040303},
      zblnumber={0795.05127},
      }
  • [book_random] Go to document S. Janson, T. Łuczak, and A. Rucinski, Random Graphs, New York: Wiley-Interscience, 2000.
    @book {book_random, MRKEY = {1782847},
      AUTHOR = {Janson, Svante and {\L}uczak, Tomasz and Rucinski, Andrzej},
      TITLE = {Random Graphs},
      SERIES = {Wiley-Interscience Ser. Discrete Math. Optimization},
      PUBLISHER = {Wiley-Interscience},
      ADDRESS={New York},
      YEAR = {2000},
      PAGES = {xii+333},
      ISBN = {0-471-17541-2},
      MRCLASS = {05C80 (60C05 82B41)},
      MRNUMBER = {1782847},
      MRREVIEWER = {Mark R. Jerrum},
      DOI = {10.1002/9781118032718},
      zblnumber={0968.05003},
      }
  • [kalai] Go to document G. Kalai, "Enumeration of ${\bf Q}$-acyclic simplicial complexes," Israel J. Math., vol. 45, iss. 4, pp. 337-351, 1983.
    @article {kalai, MRKEY = {0720308},
      AUTHOR = {Kalai, Gil},
      TITLE = {Enumeration of {${\bf Q}$}-acyclic simplicial complexes},
      JOURNAL = {Israel J. Math.},
      FJOURNAL = {Israel Journal of Mathematics},
      VOLUME = {45},
      YEAR = {1983},
      NUMBER = {4},
      PAGES = {337--351},
      ISSN = {0021-2172},
      CODEN = {ISJMAP},
      MRCLASS = {55P15 (05C05 57M15)},
      MRNUMBER = {0720308},
      MRREVIEWER = {Kenneth A. Perko, Jr.},
      DOI = {10.1007/BF02804017},
      zblnumber={0535.57011},
      }
  • [kim] 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.
    @incollection {kim, MRKEY = {2275710},
      AUTHOR = {Kim, Jeong Han},
      TITLE = {Poisson cloning model for random graphs},
      BOOKTITLE = {International {C}ongress of {M}athematicians. {V}ol. {III}},
      PAGES = {873--897},
      PUBLISHER = {Eur. Math. Soc.},
      ADDRESS={Zürich},
      YEAR = {2006},
      MRCLASS = {05C80 (60C05)},
      MRNUMBER = {2275710},
      MRREVIEWER = {Deryk Osthus},
      zblnumber={1100.05093},
      }
  • [hypOrient] 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.
    @inproceedings {hypOrient, MRKEY = {3205213},
      AUTHOR = {Lelarge, M.},
      TITLE = {A new approach to the orientation of random hypergraphs},
      BOOKTITLE = {Proceedings of the {T}wenty-{T}hird {A}nnual {ACM}-{SIAM} {S}ymposium on {D}iscrete {A}lgorithms},
      PAGES = {251--264},
      PUBLISHER = {ACM},
      ADDRESS={New York},
      YEAR = {2012},
      MRCLASS = {05C65 (05C20)},
      MRNUMBER = {3205213},
      }
  • [lin_mes] Go to document N. Linial and R. Meshulam, "Homological connectivity of random 2-complexes," Combinatorica, vol. 26, iss. 4, pp. 475-487, 2006.
    @article {lin_mes, MRKEY = {2260850},
      AUTHOR = {Linial, Nathan and Meshulam, Roy},
      TITLE = {Homological connectivity of random 2-complexes},
      JOURNAL = {Combinatorica},
      FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      VOLUME = {26},
      YEAR = {2006},
      NUMBER = {4},
      PAGES = {475--487},
      ISSN = {0209-9683},
      MRCLASS = {55M99 (05C80 55U35)},
      MRNUMBER = {2260850},
      MRREVIEWER = {Igor Rivin},
      DOI = {10.1007/s00493-006-0027-9},
      zblnumber={1121.55013},
      }
  • [LNPR] N. Linial, I. Newman, Y. Peled, and Y. Rabinovich, Extremal problems on shadows and hypercuts in simplicial complexes, 2014.
    @misc{LNPR,
      author={Linial, Nathan and Newman, Ilan and Peled, Yuval and Rabinovich, Yuri},
      TITLE={Extremal problems on shadows and hypercuts in simplicial complexes},
      ARXIV={1408.0602},
      YEAR={2014},
      }
  • [lyo_asym] Go to document R. Lyons, "Asymptotic enumeration of spanning trees," Combin. Probab. Comput., vol. 14, iss. 4, pp. 491-522, 2005.
    @article {lyo_asym, MRKEY = {2160416},
      AUTHOR = {Lyons, Russell},
      TITLE = {Asymptotic enumeration of spanning trees},
      JOURNAL = {Combin. Probab. Comput.},
      FJOURNAL = {Combinatorics, Probability and Computing},
      VOLUME = {14},
      YEAR = {2005},
      NUMBER = {4},
      PAGES = {491--522},
      ISSN = {0963-5483},
      MRCLASS = {05C05 (05C50 60C05 60G50)},
      MRNUMBER = {2160416},
      MRREVIEWER = {Tatiana Smirnova-Nagnibeda},
      DOI = {10.1017/S096354830500684X},
      zblnumber={1076.05007},
      }
  • [azuma] Go to document C. McDiarmid, "On the method of bounded differences," in Surveys in Combinatorics, 1989, Cambridge: Cambridge Univ. Press, 1989, vol. 141, pp. 148-188.
    @incollection {azuma, MRKEY = {1036755},
      AUTHOR = {McDiarmid, Colin},
      TITLE = {On the method of bounded differences},
      BOOKTITLE = {Surveys in Combinatorics, 1989},
      VENUE={{N}orwich, 1989},
      SERIES = {London Math. Soc. Lecture Note Ser.},
      VOLUME = {141},
      PAGES = {148--188},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS={Cambridge},
      YEAR = {1989},
      MRCLASS = {05C80 (60E15 60F10 60G42)},
      MRNUMBER = {1036755},
      MRREVIEWER = {Alan M. Frieze},
      zblnumber={0712.05012},
      doi = {10.1017/CBO9781107359949.008},
     }
  • [mesh_wallach] Go to document R. Meshulam and N. Wallach, "Homological connectivity of random $k$-dimensional complexes," Random Structures Algorithms, vol. 34, iss. 3, pp. 408-417, 2009.
    @article {mesh_wallach, MRKEY = {2504405},
      AUTHOR = {Meshulam, R. and Wallach, N.},
      TITLE = {Homological connectivity of random {$k$}-dimensional complexes},
      JOURNAL = {Random Structures Algorithms},
      FJOURNAL = {Random Structures \& Algorithms},
      VOLUME = {34},
      YEAR = {2009},
      NUMBER = {3},
      PAGES = {408--417},
      ISSN = {1042-9832},
      MRCLASS = {60B15 (05C80 60E10 60E15)},
      MRNUMBER = {2504405},
      DOI = {10.1002/rsa.20238},
      zblnumber={1177.55011},
      }
  • [mohar] Go to document B. Mohar, "The spectrum of an infinite graph," Linear Algebra Appl., vol. 48, pp. 245-256, 1982.
    @article {mohar, MRKEY = {0683222},
      AUTHOR = {Mohar, Bojan},
      TITLE = {The spectrum of an infinite graph},
      JOURNAL = {Linear Algebra Appl.},
      FJOURNAL = {Linear Algebra and its Applications},
      VOLUME = {48},
      YEAR = {1982},
      PAGES = {245--256},
      ISSN = {0024-3795},
      CODEN = {LAAPAW},
      MRCLASS = {05C50},
      MRNUMBER = {0683222},
      MRREVIEWER = {H. A. Jung},
      DOI = {10.1016/0024-3795(82)90111-2},
      zblnumber={0502.05040},
      }
  • [molloy] Go to document M. Molloy, "Cores in random hypergraphs and Boolean formulas," Random Structures Algorithms, vol. 27, iss. 1, pp. 124-135, 2005.
    @article {molloy, MRKEY = {2150018},
      AUTHOR = {Molloy, Michael},
      TITLE = {Cores in random hypergraphs and {B}oolean formulas},
      JOURNAL = {Random Structures Algorithms},
      FJOURNAL = {Random Structures \& Algorithms},
      VOLUME = {27},
      YEAR = {2005},
      NUMBER = {1},
      PAGES = {124--135},
      ISSN = {1042-9832},
      MRCLASS = {05C80 (60C05 68R10)},
      MRNUMBER = {2150018},
      MRREVIEWER = {Andrzej Ruci{ń}ski},
      DOI = {10.1002/rsa.20061},
      zblnumber={1068.05063},
      }
  • [pittel] Go to document B. Pittel and G. B. Sorkin, "The satisfiability threshold for $k$-XORSAT," Combin. Probab. Comput., vol. 25, iss. 2, pp. 236-268, 2016.
    @article {pittel, MRKEY = {3455676},
      AUTHOR = {Pittel, Boris and Sorkin, Gregory B.},
      TITLE = {The satisfiability threshold for {$k$}-{XORSAT}},
      JOURNAL = {Combin. Probab. Comput.},
      FJOURNAL = {Combinatorics, Probability and Computing},
      VOLUME = {25},
      YEAR = {2016},
      NUMBER = {2},
      PAGES = {236--268},
      ISSN = {0963-5483},
      MRCLASS = {68Q87 (05A16 60B20)},
      MRNUMBER = {3455676},
      DOI = {10.1017/S0963548315000097},
      }
  • [book_unbounded] M. Reed and B. Simon, Methods of Modern Mathematical Physics. I: Functional Analysis, Second ed., New York: Academic Press [Harcourt Brace Jovanovich, Publishers], 1980.
    @book {book_unbounded, MRKEY = {0751959},
      AUTHOR = {Reed, Michael and Simon, Barry},
      TITLE = {Methods of Modern Mathematical Physics. {I}: Functional Analysis},
      EDITION = {Second},
      PUBLISHER = {Academic Press [Harcourt Brace Jovanovich, Publishers]},
      ADDRESS={New York},
      YEAR = {1980},
      PAGES = {xv+400},
      ISBN = {0-12-585050-6},
      MRCLASS = {46-01 (47-01)},
      MRNUMBER = {0751959},
      zblnumber={0459.46001},
      }
  • [salez] Go to document J. Salez, Some implications of local weak convergence for large random graphs, 2011.
    @misc{salez,
      author={Salez, Justin},
      TITLE={ Some implications of local weak convergence for large random graphs},
      NOTE={Ph.D. thesis, Université-Pierre-et-Marie-Curie},
      YEAR={2011},
      URL = {https://hal.archives-ouvertes.fr/tel-00637130/document},
     }

Authors

Nathan Linial

Department of Computer Science, Hebrew University, Jerusalem, Israel

Yuval Peled

Department of Computer Science, Hebrew University, Jerusalem, Israel