The fundamental group of random 2-complexes

By Eric K. Babson, Christopher E. Hoffman, Matthew Kahle. 2007

112 citations recorded by the source corpus.

We study Linial-Meshulam random 2-complexes, which are two-dimensional analogues of Erd\H{o}s-R\'enyi 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.

Subfields: Computational Theory and Mathematics, Geometry and Topology, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/282a6a750b347d04ada609b5a9b050828e028f4c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Geometry and Topology

In Mathematical Physics

Citations in the corpus

What are higher-order networks? (2021, result): “These results got refined and extended later [12, 134, 175], for instance [187] presents analogous results for random k-dimensional complexes.”
Sharp vanishing thresholds for cohomology of random flag complexes (2012, result): “n. Theorem 1.5. (Theorem 1.1 in [4]) If X ∼ X(n,p) where ǫ > 0 is ﬁxed and 1+ǫ n ≤ p ≤ 1 n1/3+ǫ then w.h.p. π1(X) is a nontrivial hyperbolic group. Theorem 1.5 is closely related to the results in [5], where a parallel result is shown for Bernoulli random 2-complexes studied earlier by Linial and”
Coboundary expanders (2010, background): “These complexes have well-studied topological and geometric behavior ([4], [15], [3]), and they provide a template for studying a broader family of random complexes.”
Large random simplicial complexes, I (2015, methodology): “ve the complete (d − 1)-skeleton and their randomness shows only in the top dimension. Some interesting results about the topology of random 2-complexes in the Linial– Meshulam model were obtained in [1], [3], [5]. A diﬀerent model of random simplicial complexes was studied by M. Kahle [13] and by s”
Limit theorems for Betti numbers of random simplicial complexes (2010, background): “ provides a natural higher-dimensional generalization of G(n;p), which has proved extremely useful in graph theory as well as in applications. (Other higher-dimensional generalizations are studied in [2, 12, 13].) Another motivation comes from the fact that every simplicial complex is homeomorphic t”
Topology of random simplicial complexes: a survey (2013, background): “Since the influential paper [41], random complexes and their topological properties have continued to be explored by several teams of researchers [43, 7, 39, 4, 5, 35].”
On the topology of random complexes built over stationary point processes. (2012, background): “Another approach has been to consider random subgraphs of complete graphs, leading to a number of papers dealing with the topology of random complexes generalising Erdős–Rényi graphs, as in, for example, [1, 14, 21, 27, 29].”
On the phase transition in random simplicial complexes (2014, background): “The threshold for the vanishing of the fundamental group of Y 2 ( n, p ) was studied in [7].”
Spectral Gaps of Random Graphs and Applications (2012, background): “Let Ỹt denote the simplicial complex Y d t (n)[t][2] with all its isolated edges deleted.”