Souvik Dhara (MIT)

Title: Large deviation for uniform random graphs with given degree

Abstract: Large deviation on random graphs aims to provide a rigorous framework for understanding the atypical or rare events on large networks. Even for elementary network functionals such as triangle counts, proving Large Deviation Principle (LDP) was a long-standing open question. In a breakthrough paper, Chatterjee and Varadhan (2011) introduced a novel framework that embedded Erdős-Rényi random graphs into the space of graphons, and used the theory developed by Lovász and coauthors to prove an LDP on this abstract graphon space. Such a representation yields LDP for all continuous functions in the graphon space, namely subgraph counts, largest eigenvalue.

In this talk, we explore LDPs for random graphs having constraints on degrees. Even understanding the typical behavior for random graphs under degree constraints is challenging, due to absence of the edge-independence. Using the framework of Chatterjee and Varadhan, we prove an LDP for such graphs on the graphon space. This also gives accurate estimates of the asymptotic number of graphs with given degrees and given subgraph densities.

This is based on joint work with Subhabrata Sen (Harvard).