Nonlinear large deviations: Mean-field and beyond

Large deviations of nonlinear functions of adjacency matrices of sparse random graphs have gained considerable interest over the last decade. This includes popular examples like subgraph count, or the extreme eigenvalues. For the first half of the talk, we will discuss how the upper tail large deviation problem of subgraph count in a random regular graph can be reduced to a variational problem and how to solve such optimization. Next, we consider Erdos–Renyi graph $\mathcal{G}(n,p)$ in the regime of $p$ where largest eigenvalue is governed by localized statistics, such as high degree vertices. In particular, for $r \geq 1$ fixed, we will discuss the upper and lower tail probabilities of top $r$ eigenvalues jointly.

This talk is based on joint works with Bhaswar B. Bhattacharya, Amir Dembo, and Shirshendu Ganguly.