The large deviation principle for the Erd\H{o}s-R\'enyi random graph
By Sourav Chatterjee, S. Varadhan. 2010
62 citations recorded by the source corpus.
What does an Erdos-Renyi graph look like when a rare event happens? This paper answers this question when p is fixed and n tends to infinity by establishing a large deviation principle under an appropriate topology. The formulation and proof of the main result uses the recent development of the theory of graph limits by Lovasz and coauthors and Szemeredi's regularity lemma from graph theory. As a basic application of the general principle, we work out large deviations for the number of triangles in G(n,p). Surprisingly, even this simple example yields an interesting double phase transition.
Subfields: Management Science and Operations Research, Mathematical Physics
View Paper: https://www.semanticscholar.org/paper/a709a568773e15714b5ad830a924754b085dead2
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Management Science and Operations Research
In Mathematical Physics
- Amir Dembo
- Sourav Chatterjee
- Lee H. Dicker
- Nathan Ross
- Giovanni Peccati
- Ivan Nourdin
- S. Armstrong
- Jean-Christophe Mourrat
Citations in the corpus
- Matrix estimation by Universal Singular Value Thresholding (2012, background): “They have also appeared recently in large deviations [31, 32, 70] and mathematical statistics [29, 81].”
- Nonlinear large deviations (2014, methodology): “Various interesting consequences of this variational formula were proved in [12, 27].”