Sharp vanishing thresholds for cohomology of random flag complexes. (English) Zbl 1294.05195

Kahle, Matthew

Ann. Math. (2) 179, No. 3, 1085-1107 (2014).

Summary: For every \(k \geq 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 \geq 3\), there is a regime in which the random flag complex is rationally homotopy equivalent to a bouquet of \(k\)-dimensional spheres.

MSC:

05E45	Combinatorial aspects of simplicial complexes
05C80	Random graphs (graph-theoretic aspects)
05C10	Planar graphs; geometric and topological aspects of graph theory

Keywords:

random topology; sharp thresholds

Software:

MathOverflow

References:

[1]	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. · Zbl 1074.05058 · doi:10.1007/s00039-005-0516-9
[2]	N. Alon and J. H. Spencer, The Probabilistic Method, Third ed., Hoboken, NJ: John Wiley & Sons, 2008. · Zbl 1148.05001 · doi:10.1002/9780470277331
[3]	L. Aronshtam and N. Linial, When does the top homology of a random simplicial complex vanish?. · Zbl 1326.55019 · doi:10.1002/rsa.20495
[4]	E. Babson, Fundamental groups of random clique complexes, 2012.
[5]	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. · Zbl 1270.20042 · doi:10.1090/S0894-0347-2010-00677-7
[6]	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. · Zbl 0897.22007 · doi:10.1007/s000390050022
[7]	A. Björner, ”Topological methods,” in Handbook of Combinatorics, Vol. 1, 2, Amsterdam: Elsevier, 1995, pp. 1819-1872. · Zbl 0851.52016
[8]	B. Bollobás, Random Graphs, Second ed., Cambridge: Cambridge Univ. Press, 2001, vol. 73. · Zbl 0979.05003 · doi:10.1017/CBO9780511814068
[9]	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. · Zbl 0376.22009 · doi:10.1007/BFb0066362
[10]	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. · Zbl 1237.55009 · doi:10.1007/s00454-011-9378-0
[11]	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. · Zbl 1275.05049 · doi:10.4310/JOC.2013.v4.n2.a4
[12]	D. Dotterrer and M. Kahle, ”Coboundary expanders,” J. Topol. Anal., vol. 4, iss. 4, pp. 499-514, 2012. · Zbl 1259.05151 · doi:10.1142/S1793525312500197
[13]	P. ErdHos and A. Rényi, ”On random graphs. I,” Publ. Math. Debrecen, vol. 6, pp. 290-297, 1959. · Zbl 0092.15705
[14]	R. Forman, ”A user’s guide to discrete Morse theory,” Sém. Lothar. Combin., vol. 48, p. 48, 2002. · Zbl 1048.57015
[15]	H. Garland, ”\(p\)-adic curvature and the cohomology of discrete subgroups of \(p\)-adic groups,” Ann. of Math., vol. 97, pp. 375-423, 1973. · Zbl 0262.22010 · doi:10.2307/1970829
[16]	A. Hatcher, Algebraic Topology, Cambridge: Cambridge Univ. Press, 2002. · Zbl 1044.55001
[17]	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. · Zbl 0051.00903 · doi:10.1215/S0012-7094-53-02004-3
[18]	C. Hoffman, M. Kahle, and E. Paquette, Spectral gaps of random graphs and applications to random topology, 2013.
[19]	S. Janson, T. Łuczak, and A. Rucinski, Random Graphs, Wiley-Interscience, New York, 2000. · Zbl 0968.05003 · doi:10.1002/9781118032718
[20]	M. Kahle, ”Topology of random clique complexes,” Discrete Math., vol. 309, iss. 6, pp. 1658-1671, 2009. · Zbl 1215.05163 · doi:10.1016/j.disc.2008.02.037
[21]	G. Kalai, ”Enumeration of \({\mathbf Q}\)-acyclic simplicial complexes,” Israel J. Math., vol. 45, iss. 4, pp. 337-351, 1983. · Zbl 0535.57011 · doi:10.1007/BF02804017
[22]	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. · Zbl 1222.55005 · doi:10.1090/S0002-9939-2010-10596-8
[23]	N. Linial and R. Meshulam, ”Homological connectivity of random 2-complexes,” Combinatorica, vol. 26, iss. 4, pp. 475-487, 2006. · Zbl 1121.55013 · doi:10.1007/s00493-006-0027-9
[24]	R. Meshulam and N. Wallach, ”Homological connectivity of random \(k\)-dimensional complexes,” Random Structures Algorithms, vol. 34, iss. 3, pp. 408-417, 2009. · Zbl 1177.55011 · doi:10.1002/rsa.20238
[25]	B. Pittel, ”A random graph with a subcritical number of edges,” Trans. Amer. Math. Soc., vol. 309, iss. 1, pp. 51-75, 1988. · Zbl 0658.05062 · doi:10.2307/2001158
[26]	. J-P. Serre, ”Groupes d’homotopie et classes de groupes abéliens,” Ann. of Math., vol. 58, pp. 258-294, 1953. · Zbl 0052.19303 · doi:10.2307/1969789
[27]	E. Wofseyphantomx(mathoverflow.net/users/75), Sufficient conditions for rational homotopy equivalence.
[28]	A. \DZuk, ”Property (T) and Kazhdan constants for discrete groups,” Geom. Funct. Anal., vol. 13, iss. 3, pp. 643-670, 2003. · Zbl 1036.22004 · doi:10.1007/s00039-003-0425-8