We consider an inhomogeneous Erd\H{ o}s-R\'enyi random graph $G_N$ with vertex set $[N] = \{ 1,\dots,N\}$ for which the pair of vertices $i,j \in [N]$, $i\neq j$, is connected by an edge with probability $r_N(\tfrac{ i}{ N},\tfrac{ j}{ N})$, independently of other pairs of vertices. Here, $r_N\colon\,[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} \|r_N-r\|_\infty = 0$ for some limiting graphon $r\colon\,[0,1]^2 \to (0,1)$, then $\lambda_N/N$ satisfies a downward LDP with rate $\binom{ N}{ 2}$ and an upward LDP with rate $N$. We identify the associated rate functions $\psi_r$ and $\widehat{ \psi}_r$, and derive their basic properties.
Categories: math.PR math.FA