Square percolation and the threshold for quadratic divergence in random right‐angled Coxeter groups. Issue 4 (24th September 2021)

• Record Type: Journal Article
• Authors: Behrstock, Jason; Falgas‐Ravry, Victor; Susse, Tim
• Is Part Of: Random structures & algorithms. Volume 60:Issue 4(2022)
• Page Start: 594
• Page End: 630
• Publication Date: 2021-09-24
• Subjects: divergence -- geometric group theory -- random graphs -- random groups -- right‐angled Coxeter groups -- square percolation; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21049
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Given a graph Γ, its auxiliary square‐graph □ ( Γ ) is the graph whose vertices are the non‐edges of Γ and whose edges are the pairs of non‐edges which induce a square (i.e., a 4‐cycle) in Γ . We determine the threshold edge‐probability p = p c ( n ) at which the Erdős–Rényi random graph Γ = Γ n, p begins to asymptotically almost surely (a.a.s.) have a square‐graph with a connected component whose squares together cover all the vertices of Γ n, p . We show p c ( n ) = 6 − 2 / n, a polylogarithmic improvement on earlier bounds on p c ( n ) due to Hagen and the authors. As a corollary, we determine the threshold p = p c ( n ) at which the random right‐angled Coxeter group W Γ n, p a.a.s. becomes strongly algebraically thick of order 1 and has quadratic divergence.