Visiting Speaker
Souvik Dhara
MIT/Microsoft Research
Large deviation for uniform random graphs with given degree
Tuesday
Jul 23, 2019
Watch video
2:00 pm
177 Huntington Ave
11th floor

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 Vardhan, 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).

About the speaker
Visiting Speaker
Souvik Dhara
MIT/Microsoft Research
Large deviation for uniform random graphs with given degree
Tue
Jul 23, 2019
2:00 pm
177 Huntington Ave
11th floor
ADD to calendar

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 Vardhan, 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).

about the speaker
10/2/19
Jaime Settle
Title TBA
10/16/19
Helder Nakaya
Title TBA