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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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},
} -
@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},
}