Large deviation principle for the norm of the Laplacian matrix 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_N(\frac{i}{N},\frac{j}{N})$, independently of other pairs of vertices. Here, $r_N:[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 Laplacian matrix of $G_N$. We show that if ${\lim }_{N\to \infty }\Vert r_N-r{\Vert }_{\infty }=0$ for some limiting graphon $r:[0,1{]}^2\to (0,1)$, then ${\lambda }_N/N$ satisfies a downward LDP with rate $\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ and an upward LDP with rate $N$. We identify the associated rate functions ${\psi }_r$ and ${\hat{\psi }}_r$, and derive their basic properties.

25 pages. Assumptions improved and minor corrections incorporated. To appear in Electronic Journal of Probability