Large Deviation Principle for the Norm of the Adjacency Matrix and the Laplacian Matrix of Inhomogeneous Erd\H{o}s-R\'enyi Random Graphs

          @misc{ scivideos_22612,
            doi = {},
            url = {https://old.simons.berkeley.edu/node/22612},
            author = {},
            keywords = {},
            language = {en},
            title = {Large Deviation Principle for the Norm of the Adjacency Matrix and the Laplacian Matrix of Inhomogeneous Erd\H{o}s-R\'enyi Random Graphs},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2022},
            month = {sep},
            note = {22612 see, \url{https://scivideos.org/index.php/simons-institute/22612}}
          }
          

Abstract

Abstract 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(\tfrac{i}{N},\tfrac{j}{N})$, independently of other pairs of vertices. Here, $r\colon\,[0,1]^2 \to (0,1)$ is a symmetric function that plays the role of a reference graphon. (1) Let $\lambda_N$ be the maximal eigenvalue of the \emph{adjacency matrix} of $G_N$. It is known that $\lambda_N/N$ satisfies an LDP with rate $N$ 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 basic properties of $\psi_r$, especially when the reference graphon $r$ is of rank 1. (2) Let $\hat\lambda_N$ be the maximal eigenvalue of the \emph{Laplacian matrix} of $G_N$. We show that $\hat\lambda_N/N$ satisfies a downward LDP with rate $\binom{N}{2}$ and an upward LDP with rate $N$. The associated rate functions $\hat\psi_r$ and $\hat\psi^*_r$ are those of the downward LDP and upward LDP for the maximal degree in the graph. We identify the basic properties of both $hat\psi_r$ and $\hat\psi^*_r$.