Large deviations for random networks and applications
Shirshendu Ganguly
While large deviations theory for sums and other linear functions of independent random variables is well developed and classical, the set of tools to analyze non-linear functions, such as polynomials, is limited. Canonical examples of such non-linear functions include subgraph counts and spectral observables in random networks.
In this series of lectures we will review the recent exciting developments around building a suitable nonlinear large deviations theory to treat such random variables and understand geometric properties of large random networks conditioned on associated rare events.
We will start with a discussion on dense graphs and see how the theory of graphons provides a natural framework to study large deviations in this setting. We will then primarily focus on sparse graphs and the new technology needed to treat them. Finally, we will see how the above and new ideas can be used to study spectral properties in this context. If time permits, we will also discuss Exponential random graphs, a well known family of Gibbs measures on graphs, and the bearing this theory has on them.
The lectures will aim to offer a glimpse of the different ideas and tools that come into play including from extremal graph theory, arithmetic combinatorics and spectral graph theory. Several open problems will also be discussed throughout the course.
The lectures will not assume anything beyond familiarity with basic probabilistic concepts.