Extremal eigenvalues of critical Erdős-Rényi graphs

Jeudi 16 janvier 15:45-16:45 - Raphael Ducatez - Genève

Résumé : We analyse the extremal eigenvalues of the adjacency matrix A of the Erdos-Renyi graph G(N, d/N). It is well known that the spectral measure of the rescaled and normalized matrix follows the semi-circle law. However this does not imply that all the eigenvalues are contained inside [-2,2]. In fact a transition occurs at d= 1/(2log(2)-1) log(N). For larger d, all the eigenvalues stay inside the bulk [-2,2]. For smaller d, we have a one-to-one correspondence between vertices of degree larger than 2d and eigenvalues outside of [-2,2]. The key ingredients of the proof are a tridiagonal representation of the matrix, and a bound on the spectral radius of the non backtracking matrix with an Ihara-Bass formula. This is a joint work with Antti Knowles and Johannes Alt.

Extremal eigenvalues of critical Erdős-Rényi graphs  Version PDF