Sharp vanishing thresholds for cohomology of random flag complexes

Matthew Kahle

doi:https://doi.org/10.4007/annals.2014.179.3.5

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.

Show/hide bibliography for this article

[ABM] $Go to document$ 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.

Show bibtex

@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] $Go to document$ N. Alon and J. H. Spencer, The Probabilistic Method, Third ed., Hoboken, NJ: John Wiley & Sons, 2008.

Show bibtex

@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] $Go to document$ L. Aronshtam and N. Linial, When does the top homology of a random simplicial complex vanish?.

Show bibtex

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

Show bibtex

@misc{babson, author={Babson, E.}, TITLE={Fundamental groups of random clique complexes}, YEAR={2012}, ARXIV={1207.5028}, }
[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.

Show bibtex

@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] $Go to document$ 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.

Show bibtex

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

Show bibtex

@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}, }
[Bollo] $Go to document$ B. Bollobás, Random Graphs, Second ed., Cambridge: Cambridge Univ. Press, 2001, vol. 73.

Show bibtex

@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] $Go to document$ 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.

Show bibtex

@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] $Go to document$ 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.

Show bibtex

@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] $Go to document$ 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.

Show bibtex

@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] $Go to document$ D. Dotterrer and M. Kahle, "Coboundary expanders," J. Topol. Anal., vol. 4, iss. 4, pp. 499-514, 2012.

Show bibtex

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

Show bibtex

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

Show bibtex

@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] $Go to document$ H. Garland, "$p$-adic curvature and the cohomology of discrete subgroups of $p$-adic groups," Ann. of Math., vol. 97, pp. 375-423, 1973.

Show bibtex

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

Show bibtex

@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] $Go to document$ 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.

Show bibtex

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

Show bibtex

@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] $Go to document$ S. Janson, T. Łuczak, and A. Rucinski, Random Graphs, Wiley-Interscience, New York, 2000.

Show bibtex

@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] $Go to document$ M. Kahle, "Topology of random clique complexes," Discrete Math., vol. 309, iss. 6, pp. 1658-1671, 2009.

Show bibtex

@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] $Go to document$ G. Kalai, "Enumeration of ${\bf Q}$-acyclic simplicial complexes," Israel J. Math., vol. 45, iss. 4, pp. 337-351, 1983.

Show bibtex

@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] $Go to document$ 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.

Show bibtex

@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] $Go to document$ N. Linial and R. Meshulam, "Homological connectivity of random 2-complexes," Combinatorica, vol. 26, iss. 4, pp. 475-487, 2006.

Show bibtex

@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] $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.

Show bibtex

@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] $Go to document$ B. Pittel, "A random graph with a subcritical number of edges," Trans. Amer. Math. Soc., vol. 309, iss. 1, pp. 51-75, 1988.

Show bibtex

@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] $Go to document$ . J-P. Serre, "Groupes d’homotopie et classes de groupes abéliens," Ann. of Math., vol. 58, pp. 258-294, 1953.

Show bibtex

@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] $Go to document$ E. Wofseyphantomx(mathoverflow.net/users/75), Sufficient conditions for rational homotopy equivalence.

Show bibtex

@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] $Go to document$ A. Żuk, "Property (T) and Kazhdan constants for discrete groups," Geom. Funct. Anal., vol. 13, iss. 3, pp. 643-670, 2003.

Show bibtex

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

Sharp vanishing thresholds for cohomology of random flag complexes

Abstract

Authors