The fundamental group of random 2-complexes

Babson, Eric; Hoffman, Christopher; Kahle, Matthew

doi:10.1090/S0894-0347-2010-00677-7

The fundamental group of random $2$-complexes
HTML articles powered by AMS MathViewer

by Eric Babson, Christopher Hoffman and Matthew Kahle

J. Amer. Math. Soc. 24 (2011), 1-28

DOI: https://doi.org/10.1090/S0894-0347-2010-00677-7

Published electronically: August 30, 2010

PDF | Request permission

Abstract:

We study Linial-Meshulam random $2$-complexes $Y(n,p)$, which are $2$-dimensional analogues of Erdős-Rényi random graphs. We find the threshold for simple connectivity to be $p = n^{-1/2}$. This is in contrast to the threshold for vanishing of the first homology group, which was shown earlier by Linial and Meshulam to be $p = 2 \log n / n$.

We use a variant of Gromov’s local-to-global theorem for linear isoperimetric inequalities to show that when $p = O( n^{-1/2 -\epsilon }$), the fundamental group is word hyperbolic. Along the way we classify the homotopy types of sparse $2$-dimensional simplicial complexes and establish isoperimetric inequalities for such complexes. These intermediate results do not involve randomness and may be of independent interest.

References

Béla Bollobás, Random graphs, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001. MR 1864966, DOI 10.1017/CBO9780511814068
B. H. Bowditch, A short proof that a subquadratic isoperimetric inequality implies a linear one, Michigan Math. J. 42 (1995), no. 1, 103–107. MR 1322192, DOI 10.1307/mmj/1029005156
P. Erdős and A. Rényi, On random graphs. I, Publ. Math. Debrecen 6 (1959), 290–297. MR 120167, DOI 10.5486/pmd.1959.6.3-4.12
Ehud Friedgut and Gil Kalai, Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc. 124 (1996), no. 10, 2993–3002. MR 1371123, DOI 10.1090/S0002-9939-96-03732-X
M. Gromov, Hyperbolic groups, Essays in group theory, Math. Sci. Res. Inst. Publ., vol. 8, Springer, New York, 1987, pp. 75–263. MR 919829, DOI 10.1007/978-1-4613-9586-7_{3}
M. Gromov, Asymptotic invariants of infinite groups, Geometric group theory, Vol. 2 (Sussex, 1991) London Math. Soc. Lecture Note Ser., vol. 182, Cambridge Univ. Press, Cambridge, 1993, pp. 1–295. MR 1253544
Allen Hatcher, Algebraic topology, Cambridge University Press, Cambridge, 2002. MR 1867354
Matthew Kahle, The neighborhood complex of a random graph, J. Combin. Theory Ser. A 114 (2007), no. 2, 380–387. MR 2293099, DOI 10.1016/j.jcta.2006.05.004
Matthew Kahle, Topology of random clique complexes, Discrete Math. 309 (2009), no. 6, 1658–1671. MR 2510573, DOI 10.1016/j.disc.2008.02.037
Nathan Linial and Roy Meshulam, Homological connectivity of random 2-complexes, Combinatorica 26 (2006), no. 4, 475–487. MR 2260850, DOI 10.1007/s00493-006-0027-9
R. Meshulam and N. Wallach, Homological connectivity of random $k$-dimensional complexes, Random Structures Algorithms 34 (2009), no. 3, 408–417. MR 2504405, DOI 10.1002/rsa.20238
Yann Ollivier, A January 2005 invitation to random groups, Ensaios Matemáticos [Mathematical Surveys], vol. 10, Sociedade Brasileira de Matemática, Rio de Janeiro, 2005. MR 2205306
P. Papasoglu, An algorithm detecting hyperbolicity, Geometric and computational perspectives on infinite groups (Minneapolis, MN and New Brunswick, NJ, 1994) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 25, Amer. Math. Soc., Providence, RI, 1996, pp. 193–200. MR 1364185, DOI 10.1090/dimacs/025/10
Nicholas Pippenger and Kristin Schleich, Topological characteristics of random triangulated surfaces, Random Structures Algorithms 28 (2006), no. 3, 247–288. MR 2213112, DOI 10.1002/rsa.20080
A. Żuk, Property (T) and Kazhdan constants for discrete groups, Geom. Funct. Anal. 13 (2003), no. 3, 643–670. MR 1995802, DOI 10.1007/s00039-003-0425-8