Sharp vanishing thresholds for cohomology of random flag complexes

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.

Note: To view the article, click on the URL link for the DOI number.

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

Authors

Matthew Kahle

Department of Mathematics, The Ohio State University, Columbus, OH 43202