Lack of Hyperbolicity in Asymptotic Erdös--Renyi Sparse Random Graphs

Abstract

In this work we prove that the giant component of the Erdös--Renyi random graph $G(n,c/n)$ for c a constant greater than 1 (sparse regime), is not Gromov $\delta$-hyperbolic for any positive $\delta$ with probability tending to one as $n\to \infty$. As a corollary we provide an alternative proof that the giant component of $G(n,c/n)$ when c>1 has zero spectral gap almost surely as $n\to \infty$.

Updated version with improved results and narrative

References in corpus (2)

• Random graphs containing arbitrary distributions of subgraphs
• The Large Scale Curvature of Networks

Cited by in corpus (1)

• On the Hyperbolicity of Small-World and Tree-Like Random Graphs