Séminaire de Probabilités commun ICJ/UMPA

Spectrum of critical Erdős-Rényi graphs

par Raphael Ducatez

Europe/Paris
e-UMPA (ENS)

e-UMPA

ENS

Description

We analyse the spectrum of the (scaled) adjacency matrix A of the Erdős-Rényi graph G(N, d/N) in the critical regime d = b log N. We establish a one-to-one correspondence between vertices of degree at least 2d and nontrivial eigenvalues outside the asymptotic bulk [−2, 2]. This correspondence implies a transition at an explicit b*. For d>b* log N the spectrum is just the bulk [−2, 2] and the eigenvectors are completely delocalized. For d< b* log N another phase appears. The spectrum outside [−2, 2] is not empty and there the eigenvectors concentrate around the large degree vertices.

(Joint work with Antti Knowles and Johannes Alt)