Abstract
For every $k \ge 1$, the $k$-th cohomology group $H^k(X, \mathbb{Q})$ of the random flag complex $X \sim X(n,p)$ passes through two phase transitions: one where it appears and one where it vanishes. We describe the vanishing threshold and show that it is sharp. Using the same spectral methods, we also find a sharp threshold for the fundamental group $\pi_1(X)$ to have Kazhdan’s property~(T). Combining with earlier results, we obtain as a corollary that for every $k \ge 3$, there is a regime in which the random flag complex is rationally homotopy equivalent to a bouquet of $k$-dimensional spheres.
-
[ABM]
R. Aharoni, E. Berger, and R. Meshulam, "Eigenvalues and homology of flag complexes and vector representations of graphs," Geom. Funct. Anal., vol. 15, iss. 3, pp. 555-566, 2005.
@article {ABM, MRKEY = {2221142},
AUTHOR = {Aharoni, R. and Berger, E. and Meshulam, R.},
TITLE = {Eigenvalues and homology of flag complexes and vector representations of graphs},
JOURNAL = {Geom. Funct. Anal.},
FJOURNAL = {Geometric and Functional Analysis},
VOLUME = {15},
YEAR = {2005},
NUMBER = {3},
PAGES = {555--566},
ISSN = {1016-443X},
CODEN = {GFANFB},
MRCLASS = {05C69 (05C65)},
MRNUMBER = {2221142},
MRREVIEWER = {Nigel Martin},
ZBLNUMBER = {1074.05058},
DOI = {10.1007/s00039-005-0516-9},
} -
[Alon]
N. Alon and J. H. Spencer, The Probabilistic Method, Third ed., Hoboken, NJ: John Wiley & Sons, 2008.
@book {Alon, MRKEY = {2437651},
AUTHOR = {Alon, Noga and Spencer, Joel H.},
TITLE = {The Probabilistic Method},
SERIES = {Wiley-Interscience Ser. Discrete Math. and Optimization},
EDITION = {Third},
NOTE = {with an appendix on the life and work of Paul Erd{ő}s},
PUBLISHER = {John Wiley \& Sons},
ADDRESS = {Hoboken, NJ},
YEAR = {2008},
PAGES = {xviii+352},
ISBN = {978-0-470-17020-5},
MRCLASS = {60-02 (05C80 60C05 60F99 60G42)},
MRNUMBER = {2437651},
ZBLNUMBER = {1148.05001},
DOI = {10.1002/9780470277331},
} -
[AL13]
L. Aronshtam and N. Linial, When does the top homology of a random simplicial complex vanish?.
@misc{AL13,
author = {Aronshtam, L. and Linial, N.},
TITLE = {When does the top homology of a random simplicial complex vanish?},
SORTYEAR={2013},
NOTE={\emph{Random Structures Algorithms},
published online 12 Mar 2013},
DOI={10.1002/rsa.20495},
} -
[babson] E. Babson, Fundamental groups of random clique complexes, 2012.
@misc{babson,
author={Babson, E.},
TITLE={Fundamental groups of random clique complexes},
YEAR={2012},
ARXIV={1207.5028},
} -
[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},
ZBLNUMBER = {1270.20042},
DOI = {10.1090/S0894-0347-2010-00677-7},
} -
[Ballmann]
W. Ballmann and J. Świpolhkatkowski, "On $L^2$-cohomology and property (T) for automorphism groups of polyhedral cell complexes," Geom. Funct. Anal., vol. 7, iss. 4, pp. 615-645, 1997.
@article {Ballmann, MRKEY = {1465598},
AUTHOR = {Ballmann, W. and {\'S}wi{\polhk{a}}tkowski, J.},
TITLE = {On {$L\sp 2$}-cohomology and property ({T}) for automorphism groups of polyhedral cell complexes},
JOURNAL = {Geom. Funct. Anal.},
FJOURNAL = {Geometric and Functional Analysis},
VOLUME = {7},
YEAR = {1997},
NUMBER = {4},
PAGES = {615--645},
ISSN = {1016-443X},
CODEN = {GFANFB},
MRCLASS = {20F32 (20J05 22D10 53C23 57M07)},
MRNUMBER = {1465598},
MRREVIEWER = {Alain Valette},
ZBLNUMBER = {0897.22007},
DOI = {10.1007/s000390050022},
} -
[Bjorner] A. Björner, "Topological methods," in Handbook of Combinatorics, Vol. 1, 2, Amsterdam: Elsevier, 1995, pp. 1819-1872.
@incollection {Bjorner, MRKEY = {1373690},
AUTHOR = {Bj{ö}rner, A.},
TITLE = {Topological methods},
BOOKTITLE = {Handbook of Combinatorics, {V}ol. 1, 2},
PAGES = {1819--1872},
PUBLISHER = {Elsevier},
ADDRESS = {Amsterdam},
YEAR = {1995},
MRCLASS = {52B05 (05B35 05E25 52B40)},
MRNUMBER = {1373690},
MRREVIEWER = {Andrew Vince},
ZBLNUMBER = {0851.52016},
} -
@book {Bollo, MRKEY = {1864966},
AUTHOR = {Bollob{á}s, B{é}la},
TITLE = {Random Graphs},
SERIES = {Cambridge Stud. Adv. Math.},
VOLUME = {73},
EDITION = {Second},
PUBLISHER = {Cambridge Univ. Press},
ADDRESS = {Cambridge},
YEAR = {2001},
PAGES = {xviii+498},
ISBN = {0-521-80920-7; 0-521-79722-5},
MRCLASS = {05C80 (60C05)},
MRNUMBER = {1864966},
ZBLNUMBER = {0979.05003},
DOI = {10.1017/CBO9780511814068},
} -
[Borel]
A. Borel, "Cohomologie de certains groupes discretes et laplacien $p$-adique (d’après H. Garland)," in Séminaire Bourbaki, 26e Année (1973/1974), Exp. No. 437, New York: Springer-Verlag, 1975, vol. 431, pp. 12-35.
@incollection {Borel, MRKEY = {0476919},
AUTHOR = {Borel, Armand},
TITLE = {Cohomologie de certains groupes discretes et laplacien {$p$}-adique (d'après {H}. {G}arland)},
BOOKTITLE = {Séminaire {B}ourbaki, 26e Année (1973/1974), {E}xp. {N}o. 437},
PAGES = {12--35},
SERIES={Lecture Notes in Math.},
VOLUME={431},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
YEAR = {1975},
MRCLASS = {22E40 (57F10)},
MRNUMBER = {0476919},
MRREVIEWER = {J. S. Joel},
ZBLNUMBER = {0376.22009},
DOI = {10.1007/BFb0066362},
} -
[CCFK12]
D. Cohen, A. Costa, M. Farber, and T. Kappeler, "Topology of random 2-complexes," Discrete Comput. Geom., vol. 47, iss. 1, pp. 117-149, 2012.
@article {CCFK12, MRKEY = {2886093},
AUTHOR = {Cohen, D. and Costa, A. and Farber, M. and Kappeler, T.},
TITLE = {Topology of random 2-complexes},
JOURNAL = {Discrete Comput. Geom.},
FJOURNAL = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
VOLUME = {47},
YEAR = {2012},
NUMBER = {1},
PAGES = {117--149},
ISSN = {0179-5376},
CODEN = {DCGEER},
MRCLASS = {57M20 (05C80 52A22 60D05)},
MRNUMBER = {2886093},
MRREVIEWER = {Dirk Sch{ü}tz},
ZBLNUMBER = {1237.55009},
DOI = {10.1007/s00454-011-9378-0},
} -
[DHK12]
B. DeMarco, A. Hamm, and J. Kahn, "On the triangle space of a random graph," J. Comb., vol. 4, iss. 2, pp. 229-249, 2013.
@article {DHK12, MRKEY = {3096134},
AUTHOR = {DeMarco, B. and Hamm, A. and Kahn, J.},
TITLE = {On the triangle space of a random graph},
JOURNAL = {J. Comb.},
FJOURNAL = {Journal of Combinatorics},
VOLUME = {4},
YEAR = {2013},
NUMBER = {2},
PAGES = {229--249},
ISSN = {2156-3527},
MRCLASS = {05C80 (05C35 05D40 55U10 60E15)},
MRNUMBER = {3096134},
ZBLNUMBER = {1275.05049},
DOI = {10.4310/JOC.2013.v4.n2.a4},
} -
[Dotterrer12]
D. Dotterrer and M. Kahle, "Coboundary expanders," J. Topol. Anal., vol. 4, iss. 4, pp. 499-514, 2012.
@article {Dotterrer12, MRKEY = {3021774},
AUTHOR = {Dotterrer, Dominic and Kahle, Matthew},
TITLE = {Coboundary expanders},
JOURNAL = {J. Topol. Anal.},
FJOURNAL = {Journal of Topology and Analysis},
VOLUME = {4},
YEAR = {2012},
NUMBER = {4},
PAGES = {499--514},
ISSN = {1793-5253},
MRCLASS = {05C80 (11B75)},
MRNUMBER = {3021774},
MRREVIEWER = {Sebastian M. Cioab{\u{a}}},
ZBLNUMBER = {1259.05151},
DOI = {10.1142/S1793525312500197},
} -
[ER] P. ErdHos and A. Rényi, "On random graphs. I," Publ. Math. Debrecen, vol. 6, pp. 290-297, 1959.
@article {ER, MRKEY = {0120167},
AUTHOR = {Erd{ő}s, P. and R{é}nyi, A.},
TITLE = {On random graphs. {I}},
JOURNAL = {Publ. Math. Debrecen},
FJOURNAL = {Publicationes Mathematicae Debrecen},
VOLUME = {6},
YEAR = {1959},
PAGES = {290--297},
ISSN = {0033-3883},
MRCLASS = {05.00},
MRNUMBER = {0120167},
MRREVIEWER = {A. Dvoretzky},
ZBLNUMBER = {0092.15705},
} -
[Forman] R. Forman, "A user’s guide to discrete Morse theory," Sém. Lothar. Combin., vol. 48, p. 48, 2002.
@article {Forman, MRKEY = {1939695},
AUTHOR = {Forman, Robin},
TITLE = {A user's guide to discrete {M}orse theory},
JOURNAL = {Sém. Lothar. Combin.},
FJOURNAL = {Séminaire Lotharingien de Combinatoire},
VOLUME = {48},
YEAR = {2002},
PAGES = {Art. B48c, 35},
ISSN = {1286-4889},
MRCLASS = {57Q05 (57R70)},
MRNUMBER = {1939695},
MRREVIEWER = {Wolfgang K{ü}hnel},
ZBLNUMBER = {1048.57015},
} -
[Garland]
H. Garland, "$p$-adic curvature and the cohomology of discrete subgroups of $p$-adic groups," Ann. of Math., vol. 97, pp. 375-423, 1973.
@article {Garland, MRKEY = {0320180},
AUTHOR = {Garland, Howard},
TITLE = {{$p$}-adic curvature and the cohomology of discrete subgroups of {$p$}-adic groups},
JOURNAL = {Ann. of Math.},
FJOURNAL = {Annals of Mathematics. Second Series},
VOLUME = {97},
YEAR = {1973},
PAGES = {375--423},
ISSN = {0003-486X},
MRCLASS = {20J05},
MRNUMBER = {0320180},
MRREVIEWER = {M. S. Raghunathan},
ZBLNUMBER = {0262.22010},
DOI = {10.2307/1970829},
} -
[Hatcher] A. Hatcher, Algebraic Topology, Cambridge: Cambridge Univ. Press, 2002.
@book {Hatcher, MRKEY = {1867354},
AUTHOR = {Hatcher, Allen},
TITLE = {Algebraic Topology},
PUBLISHER = {Cambridge Univ. Press},
ADDRESS = {Cambridge},
YEAR = {2002},
PAGES = {xii+544},
ISBN = {0-521-79160-X; 0-521-79540-0},
MRCLASS = {55-01 (55-00)},
MRNUMBER = {1867354},
MRREVIEWER = {Donald W. Kahn},
ZBLNUMBER = {1044.55001},
} -
[HW53]
A. J. Hoffman and H. W. Wielandt, "The variation of the spectrum of a normal matrix," Duke Math. J., vol. 20, pp. 37-39, 1953.
@article {HW53, MRKEY = {0052379},
AUTHOR = {Hoffman, A. J. and Wielandt, H. W.},
TITLE = {The variation of the spectrum of a normal matrix},
JOURNAL = {Duke Math. J.},
FJOURNAL = {Duke Mathematical Journal},
VOLUME = {20},
YEAR = {1953},
PAGES = {37--39},
ISSN = {0012-7094},
MRCLASS = {09.0X},
MRNUMBER = {0052379},
MRREVIEWER = {W. Givens},
ZBLNUMBER = {0051.00903},
DOI = {10.1215/S0012-7094-53-02004-3},
} -
[hkp] C. Hoffman, M. Kahle, and E. Paquette, Spectral gaps of random graphs and applications to random topology, 2013.
@misc{hkp,
author={Hoffman, C. and Kahle, M. and Paquette, E.},
TITLE={Spectral gaps of random graphs and applications to random topology},
YEAR={2013},
ARXIV={1201.0425},
} -
[randomgraphs]
S. Janson, T. Łuczak, and A. Rucinski, Random Graphs, Wiley-Interscience, New York, 2000.
@book {randomgraphs, MRKEY = {1782847},
AUTHOR = {Janson, Svante and {\L}uczak, Tomasz and Rucinski, Andrzej},
TITLE = {Random Graphs},
SERIES = {Wiley-Interscience Ser. Discr. Math. and Optimization},
PUBLISHER = {Wiley-Interscience, New York},
YEAR = {2000},
PAGES = {xii+333},
ISBN = {0-471-17541-2},
MRCLASS = {05C80 (60C05 82B41)},
MRNUMBER = {1782847},
MRREVIEWER = {Mark R. Jerrum},
ZBLNUMBER = {0968.05003},
DOI = {10.1002/9781118032718},
} -
[clique]
M. Kahle, "Topology of random clique complexes," Discrete Math., vol. 309, iss. 6, pp. 1658-1671, 2009.
@article {clique, MRKEY = {2510573},
AUTHOR = {Kahle, Matthew},
TITLE = {Topology of random clique complexes},
JOURNAL = {Discrete Math.},
FJOURNAL = {Discrete Mathematics},
VOLUME = {309},
YEAR = {2009},
NUMBER = {6},
PAGES = {1658--1671},
ISSN = {0012-365X},
CODEN = {DSMHA4},
MRCLASS = {05C80 (05C10 58E05)},
MRNUMBER = {2510573},
MRREVIEWER = {Klas Markstr{ö}m},
ZBLNUMBER = {1215.05163},
DOI = {10.1016/j.disc.2008.02.037},
} -
[Gil]
G. Kalai, "Enumeration of ${\bf Q}$-acyclic simplicial complexes," Israel J. Math., vol. 45, iss. 4, pp. 337-351, 1983.
@article {Gil, 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.},
ZBLNUMBER = {0535.57011},
DOI = {10.1007/BF02804017},
} -
[Kozlov]
D. N. Kozlov, "The threshold function for vanishing of the top homology group of random $d$-complexes," Proc. Amer. Math. Soc., vol. 138, iss. 12, pp. 4517-4527, 2010.
@article {Kozlov, MRKEY = {2680076},
AUTHOR = {Kozlov, Dmitry N.},
TITLE = {The threshold function for vanishing of the top homology group of random {$d$}-complexes},
JOURNAL = {Proc. Amer. Math. Soc.},
FJOURNAL = {Proceedings of the American Mathematical Society},
VOLUME = {138},
YEAR = {2010},
NUMBER = {12},
PAGES = {4517--4527},
ISSN = {0002-9939},
CODEN = {PAMYAR},
MRCLASS = {55U10 (60B99)},
MRNUMBER = {2680076},
MRREVIEWER = {G{á}bor Hetyei},
ZBLNUMBER = {1222.55005},
DOI = {10.1090/S0002-9939-2010-10596-8},
} -
[LM]
N. Linial and R. Meshulam, "Homological connectivity of random 2-complexes," Combinatorica, vol. 26, iss. 4, pp. 475-487, 2006.
@article {LM, 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},
ZBLNUMBER = {1121.55013},
DOI = {10.1007/s00493-006-0027-9},
} -
[MW]
R. Meshulam and N. Wallach, "Homological connectivity of random $k$-dimensional complexes," Random Structures Algorithms, vol. 34, iss. 3, pp. 408-417, 2009.
@article {MW, 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},
ZBLNUMBER = {1177.55011},
DOI = {10.1002/rsa.20238},
} -
[P88]
B. Pittel, "A random graph with a subcritical number of edges," Trans. Amer. Math. Soc., vol. 309, iss. 1, pp. 51-75, 1988.
@article {P88, MRKEY = {0957061},
AUTHOR = {Pittel, B.},
TITLE = {A random graph with a subcritical number of edges},
JOURNAL = {Trans. Amer. Math. Soc.},
FJOURNAL = {Transactions of the American Mathematical Society},
VOLUME = {309},
YEAR = {1988},
NUMBER = {1},
PAGES = {51--75},
ISSN = {0002-9947},
CODEN = {TAMTAM},
MRCLASS = {05C80},
MRNUMBER = {0957061},
MRREVIEWER = {Zbigniew Palka},
ZBLNUMBER = {0658.05062},
DOI = {10.2307/2001158},
} -
[Serre53]
. J-P. Serre, "Groupes d’homotopie et classes de groupes abéliens," Ann. of Math., vol. 58, pp. 258-294, 1953.
@article {Serre53, MRKEY = {0059548},
AUTHOR = {Serre, {\relax J-P}},
TITLE = {Groupes d'homotopie et classes de groupes abéliens},
JOURNAL = {Ann. of Math.},
FJOURNAL = {Annals of Mathematics. Second Series},
VOLUME = {58},
YEAR = {1953},
PAGES = {258--294},
ISSN = {0003-486X},
MRCLASS = {56.0X},
MRNUMBER = {0059548},
MRREVIEWER = {W. S. Massey},
ZBLNUMBER = {0052.19303},
DOI = {10.2307/1969789},
} -
[waffle]
E. Wofseyphantomx(mathoverflow.net/users/75), Sufficient conditions for rational homotopy equivalence.
@misc{waffle,
author={Wofsey\phantom{x}(mathoverflow.net/users/75), E.},
TITLE={Sufficient conditions for rational homotopy equivalence},
NOTE={MathOverflow},
URL={http://mathoverflow.net/questions/127716},
} -
[z03]
A. Żuk, "Property (T) and Kazhdan constants for discrete groups," Geom. Funct. Anal., vol. 13, iss. 3, pp. 643-670, 2003.
@article {z03, MRKEY = {1995802},
AUTHOR = {{\.Z}uk, A.},
TITLE = {Property ({T}) and {K}azhdan constants for discrete groups},
JOURNAL = {Geom. Funct. Anal.},
FJOURNAL = {Geometric and Functional Analysis},
VOLUME = {13},
YEAR = {2003},
NUMBER = {3},
PAGES = {643--670},
ISSN = {1016-443X},
CODEN = {GFANFB},
MRCLASS = {20F65},
MRNUMBER = {1995802},
MRREVIEWER = {Stephen J. Pride},
ZBLNUMBER = {1036.22004},
DOI = {10.1007/s00039-003-0425-8},
}