×

The fundamental group of random 2-complexes. (English) Zbl 1270.20042

Summary: 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 N. Linial and R. Meshulam [Combinatorica 26, No. 4, 475-487 (2006; Zbl 1121.55013)] 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-\varepsilon})\), 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.

MSC:

20F65 Geometric group theory
55U10 Simplicial sets and complexes in algebraic topology
05C80 Random graphs (graph-theoretic aspects)
20F67 Hyperbolic groups and nonpositively curved groups
05E45 Combinatorial aspects of simplicial complexes
20F34 Fundamental groups and their automorphisms (group-theoretic aspects)
57M07 Topological methods in group theory

Citations:

Zbl 1121.55013
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Béla Bollobás, Random graphs, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001. · Zbl 0979.05003
[2] B. H. Bowditch, A short proof that a subquadratic isoperimetric inequality implies a linear one, Michigan Math. J. 42 (1995), no. 1, 103 – 107. · Zbl 0835.53051
[3] P. Erdős and A. Rényi, On random graphs. I, Publ. Math. Debrecen 6 (1959), 290 – 297. · Zbl 0092.15705
[4] Ehud Friedgut and Gil Kalai, Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc. 124 (1996), no. 10, 2993 – 3002. · Zbl 0864.05078
[5] M. Gromov, Hyperbolic groups, Essays in group theory, Math. Sci. Res. Inst. Publ., vol. 8, Springer, New York, 1987, pp. 75 – 263. · Zbl 0634.20015
[6] 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. · Zbl 0841.20039
[7] Allen Hatcher, Algebraic topology, Cambridge University Press, Cambridge, 2002. · Zbl 1044.55001
[8] Matthew Kahle, The neighborhood complex of a random graph, J. Combin. Theory Ser. A 114 (2007), no. 2, 380 – 387. · Zbl 1110.05090
[9] Matthew Kahle, Topology of random clique complexes, Discrete Math. 309 (2009), no. 6, 1658 – 1671. · Zbl 1215.05163
[10] Nathan Linial and Roy Meshulam, Homological connectivity of random 2-complexes, Combinatorica 26 (2006), no. 4, 475 – 487. · Zbl 1121.55013
[11] R. Meshulam and N. Wallach, Homological connectivity of random \?-dimensional complexes, Random Structures Algorithms 34 (2009), no. 3, 408 – 417. · Zbl 1177.55011
[12] 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. · Zbl 1163.20311
[13] 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. · Zbl 0857.20017
[14] Nicholas Pippenger and Kristin Schleich, Topological characteristics of random triangulated surfaces, Random Structures Algorithms 28 (2006), no. 3, 247 – 288. · Zbl 1145.52009
[15] A. Żuk, Property (T) and Kazhdan constants for discrete groups, Geom. Funct. Anal. 13 (2003), no. 3, 643 – 670. · Zbl 1036.22004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.