Geodesic
The fundamental group of random 2-complexes
Babson, Eric1 ; Hoffman, Christopher2 ; Kahle, Matthew3
1 Department of Mathematics, University of California at Davis, Davis, California 95616
2 Department of Mathematics, University of Washington, Seattle, Washington 98195
3 Department of Mathematics, Stanford University, Stanford, California 94305
Journal of the American Mathematical Society, Tome 24 (2011) no. 1, pp. 1-28

Voir la notice de l'article provenant de la source American Mathematical Society

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.
DOI : 10.1090/S0894-0347-2010-00677-7

Babson, Eric 1 ; Hoffman, Christopher 2 ; Kahle, Matthew 3

1 Department of Mathematics, University of California at Davis, Davis, California 95616
2 Department of Mathematics, University of Washington, Seattle, Washington 98195
3 Department of Mathematics, Stanford University, Stanford, California 94305 
@article{10_1090_S0894_0347_2010_00677_7,
     author = {Babson, Eric and Hoffman, Christopher and Kahle, Matthew},
     title = {The fundamental group of random 2-complexes},
     journal = {Journal of the American Mathematical Society},
     pages = {1--28},
     publisher = {mathdoc},
     volume = {24},
     number = {1},
     year = {2011},
     doi = {10.1090/S0894-0347-2010-00677-7},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-2010-00677-7/}
}
TY  - JOUR
AU  - Babson, Eric
AU  - Hoffman, Christopher
AU  - Kahle, Matthew
TI  - The fundamental group of random 2-complexes
JO  - Journal of the American Mathematical Society
PY  - 2011
SP  - 1
EP  - 28
VL  - 24
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-2010-00677-7/
DO  - 10.1090/S0894-0347-2010-00677-7
ID  - 10_1090_S0894_0347_2010_00677_7
ER  - 
%0 Journal Article
%A Babson, Eric
%A Hoffman, Christopher
%A Kahle, Matthew
%T The fundamental group of random 2-complexes
%J Journal of the American Mathematical Society
%D 2011
%P 1-28
%V 24
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-2010-00677-7/
%R 10.1090/S0894-0347-2010-00677-7
%F 10_1090_S0894_0347_2010_00677_7
Babson, Eric; Hoffman, Christopher; Kahle, Matthew. The fundamental group of random 2-complexes. Journal of the American Mathematical Society, Tome 24 (2011) no. 1, pp. 1-28. doi: 10.1090/S0894-0347-2010-00677-7

[1] Bollobã¡S, Bã©La Random graphs 2001

[2] Bowditch, B. H. A short proof that a subquadratic isoperimetric inequality implies a linear one Michigan Math. J. 1995 103 107

[3] Erdå‘S, P., Rã©Nyi, A. On random graphs. I Publ. Math. Debrecen 1959 290 297

[4] Friedgut, Ehud, Kalai, Gil Every monotone graph property has a sharp threshold Proc. Amer. Math. Soc. 1996 2993 3002

[5] Gromov, M. Hyperbolic groups 1987 75 263

[6] Gromov, M. Asymptotic invariants of infinite groups 1993 1 295

[7] Hatcher, Allen Algebraic topology 2002

[8] Kahle, Matthew The neighborhood complex of a random graph J. Combin. Theory Ser. A 2007 380 387

[9] Kahle, Matthew Topology of random clique complexes Discrete Math. 2009 1658 1671

[10] Linial, Nathan, Meshulam, Roy Homological connectivity of random 2-complexes Combinatorica 2006 475 487

[11] Meshulam, R., Wallach, N. Homological connectivity of random 𝑘-dimensional complexes Random Structures Algorithms 2009 408 417

[12] Ollivier, Yann A January 2005 invitation to random groups 2005

[13] Papasoglu, P. An algorithm detecting hyperbolicity 1996 193 200

[14] Pippenger, Nicholas, Schleich, Kristin Topological characteristics of random triangulated surfaces Random Structures Algorithms 2006 247 288

[15] ŻUk, A. Property (T) and Kazhdan constants for discrete groups Geom. Funct. Anal. 2003 643 670

Cité par Sources :