Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



The fundamental group of random $ 2$-complexes

Authors: Eric Babson, Christopher Hoffman and Matthew Kahle
Journal: J. Amer. Math. Soc. 24 (2011), 1-28
MSC (2010): Primary 20F65; Secondary 05C80
Published electronically: August 30, 2010
MathSciNet review: 2726597
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. Béla Bollobás.
    Random graphs, volume 73 of Cambridge Studies in Advanced Mathematics.
    Cambridge University Press, Cambridge, second edition, 2001. MR 1864966 (2002j:05132)
  • 2. B. H. Bowditch.
    A short proof that a subquadratic isoperimetric inequality implies a linear one.
    Michigan Math. J., 42(1):103-107, 1995. MR 1322192 (96b:20046)
  • 3. P. Erdős and A. Rényi.
    On random graphs. I.
    Publ. Math. Debrecen, 6:290-297, 1959. MR 0120167 (22:10924)
  • 4. Ehud Friedgut and Gil Kalai.
    Every monotone graph property has a sharp threshold.
    Proc. Amer. Math. Soc., 124(10):2993-3002, 1996. MR 1371123 (97e:05172)
  • 5. M. Gromov.
    Hyperbolic groups.
    In Essays in group theory, volume 8 of Math. Sci. Res. Inst. Publ., pages 75-263. Springer, New York, 1987. MR 919829 (89e:20070)
  • 6. M. Gromov.
    Asymptotic invariants of infinite groups.
    In Geometric group theory, Vol. 2 (Sussex, 1991), volume 182 of London Math. Soc. Lecture Note Ser., pages 1-295. Cambridge Univ. Press, Cambridge, 1993. MR 1253544 (95m:20041)
  • 7. Allen Hatcher.
    Algebraic topology.
    Cambridge University Press, Cambridge, 2002. MR 1867354 (2002k:55001)
  • 8. Matthew Kahle.
    The neighborhood complex of a random graph.
    J. Combin. Theory Ser. A, 114(2):380-387, 2007. MR 2293099 (2008a:05247)
  • 9. Matthew Kahle.
    Topology of random clique complexes.
    Discrete Math., 309(6):1658-1671, 2009. MR 2510573 (2010h:05276)
  • 10. Nathan Linial and Roy Meshulam.
    Homological connectivity of random 2-complexes.
    Combinatorica, 26(4):475-487, 2006. MR 2260850 (2007i:55004)
  • 11. R. Meshulam and N. Wallach.
    Homological connectivity of random $ k$-dimensional complexes.
    Random Structures Algorithms, 34(3):408-417, 2009. MR 2504405 (2010g:60015)
  • 12. Yann Ollivier.
    A January 2005 invitation to random groups, volume 10 of Ensaios Matemáticos [Mathematical Surveys].
    Sociedade Brasileira de Matemática, Rio de Janeiro, 2005. MR 2205306 (2007e:20088)
  • 13. P. Papasoglu.
    An algorithm detecting hyperbolicity.
    In Geometric and computational perspectives on infinite groups (Minneapolis, MN and New Brunswick, NJ, 1994), volume 25 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 193-200. Amer. Math. Soc., Providence, RI, 1996. MR 1364185 (96k:20075)
  • 14. Nicholas Pippenger and Kristin Schleich.
    Topological characteristics of random triangulated surfaces.
    Random Structures Algorithms, 28(3):247-288, 2006. MR 2213112 (2007d:52019)
  • 15. A. Żuk.
    Property (T) and Kazhdan constants for discrete groups.
    Geom. Funct. Anal., 13(3):643-670, 2003. MR 1995802 (2004m:20079)

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 20F65, 05C80

Retrieve articles in all journals with MSC (2010): 20F65, 05C80

Additional Information

Eric Babson
Affiliation: Department of Mathematics, University of California at Davis, Davis, California 95616

Christopher Hoffman
Affiliation: Department of Mathematics, University of Washington, Seattle, Washington 98195

Matthew Kahle
Affiliation: Department of Mathematics, Stanford University, Stanford, California 94305

Keywords: Random groups, hyperbolic groups
Received by editor(s): November 7, 2008
Received by editor(s) in revised form: July 9, 2010
Published electronically: August 30, 2010
Additional Notes: The second author was supported in part by NSA grant #H98230-05-1-0053 and NSF grant #DMS-0501102 and by an AMS Centennial Fellowship.
The third author was supported in part by the University of Washington’s NSF-VIGRE grant #DMS-0354131.
We would also like to thank MSRI and the Institute for Advanced Studies at the Hebrew University of Jerusalem where some of the research was done.
Article copyright: © Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society