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 Erdös-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²(n)). We also prove that in the regime p_n = d/n, for any δ >; 0 the Erdös-Renyi random graph has a positive probability of containing δ-fat triangles as n → ∞, thus showing that these graphs are asymptotically non-hyperbolic.