The large deviation principle for the Erdős-Rényi random graph

DOI10.1016/J.EJC.2011.03.014MaRDI QIDQ648962zbMATH OpenOpenAlexWikidataFDO

Authors Sourav Chatterjee, S. R. S. Varadhan

Publication date 29 November 2011

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.1946

zbMATH Keywords

regularity lemmagraph limitsnumber of trianglesdouble phase transition

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: 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.

Recommendations

• Large deviations for random graphs. École d'Été de Probabilités de Saint-Flour XLV -- 2015
• An introduction to large deviations for random graphs
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• On replica symmetry of large deviations in random graphs
• A large deviation principle for the Erdős-Rényi uniform random graph

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3181534 (Why is no real title available?)
• scientific article; zbMATH DE number 3780300 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 1022658 (Why is no real title available?)
• scientific article; zbMATH DE number 1158743 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Applications of Stein's method for concentration inequalities
• Connection matrices
• Contractors and connectors of graph algebras
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Counting graph homomorphisms
• Generalized quasirandom graphs
• Graph limits and exchangeable random graphs
• Limits of dense graph sequences
• Metrics for sparse graphs
• Paths in graphs
• Quick approximation to matrices and applications
• Random graphs with a given degree sequence
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Representations for partially exchangeable arrays of random variables
• Szemerédi's lemma for the analyst
• The missing log in large deviations for triangle counts
• The rank of connection matrices and the dimension of graph algebras

Cited in

(only showing first 100 items - show all)

• Vertex order in some large constrained random graphs
• Approximating the cumulant generating function of triangles in the Erdös-Rényi random graph
• Singularities in the entropy of asymptotically large simple graphs
• Matching polytons
• Multipodal structure and phase transitions in large constrained graphs
• Asymptotic structure of graphs with the minimum number of triangles
• scientific article; zbMATH DE number 6011074 (Why is no real title available?)
• Exponential Chebyshev inequalities for random graphons and their applications
• Phase transitions in finite random networks
• A large‐deviations principle for all the cluster sizes of a sparse Erdős–Rényi graph
• Rare events in random matrix theory
• The upper tail problem for induced 4‐cycles in sparse random graphs
• Nonlinear large deviations
• Large deviation principle for the greedy exploration algorithm over Erdős-Rényi graphs
• scientific article; zbMATH DE number 5252621 (Why is no real title available?)
• A strong law of large numbers for random biased connected graphs
• Upper tails for edge eigenvalues of random graphs
• A principle of moderate deviations for the size of the largest component in an Erdős-Rényi random graph in the supercritical case
• Large deviations for the largest eigenvalue of Gaussian networks with constant average degree
• Joint large deviation principle for some empirical measures of the \(d\)-regular random graphs
• The number of triangles in random intersection graphs
• Large deviation for uniform graphs with given degrees
• Upper tails via high moments and entropic stability
• A local central limit theorem for triangles in a random graph
• Large deviations for random graphs. École d'Été de Probabilités de Saint-Flour XLV -- 2015
• On the lower tail variational problem for random graphs
• Deviation probabilities for arithmetic progressions and irregular discrete structures
• On replica symmetry of large deviations in random graphs
• Sub-critical exponential random graphs: concentration of measure and some applications
• The large deviation principle for inhomogeneous Erdős-Rényi random graphs
• Degeneracy in sparse ERGMs with functions of degrees as sufficient statistics
• Complex networks: structure and functionality
• On the upper tail problem for random hypergraphs
• Asymptotic structure of constrained exponential random graph models
• Limit laws for the number of triangles in the generalized random graphs with random node weights
• Reciprocity in directed networks
• Matrix estimation by universal singular value thresholding
• The lower tail: Poisson approximation revisited
• On large deviation properties of Erdős-Rényi random graphs
• A large deviation principle for the Erdős-Rényi uniform random graph
• The role of topology in large deviations
• Spectral large deviations of sparse random matrices
• Regularity method and large deviation principles for the Erd\H{o}s--R\'enyi hypergraph
• Typical large graphs with given edge and triangle densities
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs
• Moderate deviations via cumulants
• Typical structure of sparse exponential random graph models
• The missing log in large deviations for triangle counts
• Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits
• Differential calculus on graphon space
• scientific article; zbMATH DE number 1943957 (Why is no real title available?)
• A large-deviations principle for all the components in a sparse inhomogeneous random graph
• Large-deviation properties of largest component for random graphs
• Ensemble equivalence for dense graphs
• A sample-path large deviation principle for dynamic Erdős-Rényi random graphs
• Bernoulli random matrices
• Large deviations of empirical neighborhood distribution in sparse random graphs
• Exponential random graphs behave like mixtures of stochastic block models
• Moderate deviations of subgraph counts in the Erdős-Rényi random graphs \(G(n,m)\) and \(G(n,p)\)
• Discrete Malliavin-Stein method: Berry-Esseen bounds for random graphs and percolation
• On the asymptotics of constrained exponential random graphs
• Sparse maximum-entropy random graphs with a given power-law degree distribution
• Large deviation principle for the maximal eigenvalue of inhomogeneous Erdős-Rényi random graphs
• Upper tail for homomorphism counts in constrained sparse random graphs
• Monochromatic subgraphs in randomly colored graphons
• Fluctuations of subgraph counts in graphon based random graphs
• A detailed investigation into near degenerate exponential random graphs
• Ground states for exponential random graphs
• On a question of Vera T. Sós about size forcing of graphons
• Nonlinear large deviations: beyond the hypercube
• On the phase transition curve in a directed exponential random graph model
• Ergodic theory on stationary random graphs
• Spectral edge in sparse random graphs: upper and lower tail large deviations
• Upper tails and independence polynomials in random graphs
• Dynamic Erdős-Rényi graphs
• Large deviation principles for empirical measures of colored random graphs
• scientific article; zbMATH DE number 7763253 (Why is no real title available?)
• Limits of multi-relational graphs
• Cut norm discontinuity of triangular truncation of graphons
• Deviation probabilities for arithmetic progressions and other regular discrete structures
• Limit theorems for exponential random graphs
• Estimating and understanding exponential random graph models
• Exponential inequalities for the number of subgraphs in the Erdös-Rényi random graph
• On the variational problem for upper tails in sparse random graphs
• Breaking of ensemble equivalence for dense random graphs under a single constraint
• Upper tail of the spectral radius of sparse Erdös-Rényi graphs
• Right-convergence of sparse random graphs
• Large deviations for mean field model in Erdős-Rényi graph
• The large deviation principle for interacting dynamical systems on random graphs
• Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime
• An introduction to large deviations for random graphs
• Rare Event Simulation Using Reversible Shaking Transformations
• A counterexample to the DeMarco-Kahn upper tail conjecture
• The phases of large networks with edge and triangle constraints
• Large deviations for subcomplex counts and Betti numbers in multiparameter simplicial complexes
• Moderate deviations in cycle count
• Replica symmetry in upper tails of mean-field hypergraphs
• Upper tails for arithmetic progressions in random subsets
• Chebyshev-type inequalities and large deviation principles

This page was built for publication: The large deviation principle for the Erdős-Rényi random graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q648962)