Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



An introduction to large deviations for random graphs

Author: Sourav Chatterjee
Journal: Bull. Amer. Math. Soc. 53 (2016), 617-642
MSC (2010): Primary 60F10, 05C80; Secondary 60C05, 05A20
Published electronically: June 24, 2016
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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édi'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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2010): 60F10, 05C80, 60C05, 05A20

Retrieve articles in all journals with MSC (2010): 60F10, 05C80, 60C05, 05A20

Additional Information

Sourav Chatterjee
Affiliation: Department of Statistics, Stanford University

Received by editor(s): April 22, 2016
Published electronically: June 24, 2016
Additional Notes: The author’s research was partially supported by NSF grant DMS-1441513
Article copyright: © Copyright 2016 American Mathematical Society