Premium
Square percolation and the threshold for quadratic divergence in random right‐angled Coxeter groups
Author(s) -
Behrstock Jason,
FalgasRavry Victor,
Susse Tim
Publication year - 2022
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21049
Subject(s) - mathematics , combinatorics , coxeter group , graph factorization , random regular graph , discrete mathematics , coxeter graph , square (algebra) , corollary , graph , voltage graph , line graph , 1 planar graph , geometry
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.