Global Structural Properties of Random Graphs. (24th December 2016) - Behrstock, Jason; Falgas-Ravry, Victor; Hagen, Mark F; Susse, Tim
Abstract: We study two global structural properties of a graph Γ, denoted AS and CFS, which arise in a natural way from geometric group theory. We study these properties in the Erdős–Rényi random graph model G(n, p), proving the existence of a sharp threshold for a random graph to have the AS property asymptotically almost surely, and giving fairly tight bounds for the corresponding threshold for the CFS property. As an application of our results, we show that for any constant p and any ΓG(n, p), the right-angled Coxeter group W_Γ asymptotically almost surely has quadratic divergence and thickness of order 1, generalizing and strengthening a result of Behrstock–Hagen–Sisto [8 ]. Indeed, we show that at a large range of densities a random right-angled Coxeter group has quadratic divergence.