Lack of spectral gap and hyperbolicity in asymptotic Erdo¨s-Renyi sparse random graphs

We show that the normalized Laplacian of the giant component of the Erdos-Renyi random graph G(n, p n ) in the regime p n = d/n for d a constant greater than 1 (sparse regime) has zero spectral gap as n → ∞. This is in contrast to earlier results showing the existence of a spectral gap when np n = O(log 2 (n)). We also prove that in the regime p n = d/n, for any δ > 0 the Erdos-Renyi random graph has a positive probability of containing δ-fat triangles as n → ∞, thus showing that these graphs are asymptotically non-hyperbolic.