An introduction to large deviations for random graphs

By Sourav Chatterjee. 2016

58 citations recorded by the source corpus.

This article gives an overview of the emerging literature on large deviations for random graphs. Written for the general mathematical audience, the article begins with a short introduction to the theory of large deviations. This is followed by a description of some large deviation questions about random graphs, and an outline of the recent progress on this topic. A more elaborate discussion follows, with a brief account of graph limit theory and its application in constructing a large deviation theory for dense random graphs. The role of Szemer\'edi's regularity lemma is explained, together with a sketch of the proof of the main large deviation result and some examples. Applications to exponential random graph models are briefly touched upon. The remainder of the paper is devoted to large deviations for sparse graphs. Since the regularity lemma is not applicable in the sparse regime, new tools are needed. Fortunately, there have been several new breakthroughs that managed to achieve the goal by an indirect method. These are discussed, together with an exposition of the underlying theory. The last section contains a list of open problems.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/ebf33d4f88dd8ab2607796d42d976a31cb54fb5a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Upper tails and independence polynomials in random graphs (2015, background): “Theorem 1.4 (Chatterjee and Dembo [7]).”
Large deviations of subgraph counts for sparse Erdős–Rényi graphs (2018, methodology): “ has the separable form f(x) = f1(x1)+···+fd(xd), so that µis itself a product measure, the naive mean ﬁeld approximation is an exact identity. The main idea introduced in [CD16] (see also the survey [Cha16]) is that the naive mean ﬁeld approximation can be rigorously justiﬁed when fhas low-complexi”