Square percolation and the threshold for quadratic divergence in random right‐angled Coxeter groups. Issue 4 (24th September 2021) - Behrstock, Jason; Falgas‐Ravry, Victor; Susse, Tim
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.