Square percolation and the threshold for quadratic divergence in random right‐angled Coxeter groups

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 , pbegins 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 showp c ( n ) =6 − 2 / n, a polylogarithmic improvement on earlier bounds onp 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 groupWΓ n , pa.a.s. becomes strongly algebraically thick of order 1 and has quadratic divergence.