Large deviation principle for the maximal eigenvalue of inhomogeneous Erdős-Rényi random graphs

Abstract

We consider an inhomogeneous Erdős-Rényi random graph $G_N$ with vertex set $[N]=\{1,\dots ,N\}$ for which the pair of vertices $i,j\in [N]$, $i\ne j$, is connected by an edge with probability $r(\frac{i}{N},\frac{j}{N})$, independently of other pairs of vertices. Here, $r:[0,1{]}^2\to (0,1)$ is a symmetric function that plays the role of a reference graphon. Let ${\lambda }_N$ be the maximal eigenvalue of the adjacency matrix of $G_N$. It is known that ${\lambda }_N/N$ satisfies a large deviation principle as $N\to \infty$. The associated rate function ${\psi }_r$ is given by a variational formula that involves the rate function $I_r$ of a large deviation principle on graphon space. We analyse this variational formula in order to identify the properties of ${\psi }_r$, specially when the reference graphon is of rank 1.

21 pages