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)

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

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)