The large deviation principle for the Erdős-Rényi random graph
From MaRDI portal
Publication:648962
DOI10.1016/J.EJC.2011.03.014zbMATH Open1230.05259arXiv1008.1946OpenAlexW2041354341WikidataQ105583608 ScholiaQ105583608MaRDI QIDQ648962FDOQ648962
Authors: Sourav Chatterjee, S. R. S. Varadhan 
Publication date: 29 November 2011
Published in: European Journal of Combinatorics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1008.1946
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
- Limits of dense graph sequences
- Title not available (Why is that?)
- Title not available (Why is that?)
- Representations for partially exchangeable arrays of random variables
- Graph limits and exchangeable random graphs
- Title not available (Why is that?)
- The rank of connection matrices and the dimension of graph algebras
- Reflection positivity, rank connectivity, and homomorphism of graphs
- Counting graph homomorphisms
- Title not available (Why is that?)
- Title not available (Why is that?)
- Random graphs with a given degree sequence
- Generalized quasirandom graphs
- Paths in graphs
- Title not available (Why is that?)
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Title not available (Why is that?)
- Quick approximation to matrices and applications
- Szemerédi's lemma for the analyst
- Contractors and connectors of graph algebras
- The missing log in large deviations for triangle counts
- Applications of Stein's method for concentration inequalities
- Title not available (Why is that?)
- Connection matrices
- Metrics for sparse graphs
Cited In (only showing first 100 items - show all)
- A principle of moderate deviations for the size of the largest component in an Erdős-Rényi random graph in the supercritical case
- Joint large deviation principle for some empirical measures of the \(d\)-regular random graphs
- Large deviations for the largest eigenvalue of Gaussian networks with constant average degree
- Large deviation for uniform graphs with given degrees
- Upper tails via high moments and entropic stability
- Deviation probabilities for arithmetic progressions and irregular discrete structures
- Sub-critical exponential random graphs: concentration of measure and some applications
- Degeneracy in sparse ERGMs with functions of degrees as sufficient statistics
- Complex networks: structure and functionality
- Limit laws for the number of triangles in the generalized random graphs with random node weights
- 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
- Typical structure of sparse exponential random graph models
- 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
- Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits
- Fluctuations of subgraph counts in graphon based random graphs
- On a question of Vera T. Sós about size forcing of graphons
- Spectral edge in sparse random graphs: upper and lower tail large deviations
- Title not available (Why is that?)
- Limits of multi-relational graphs
- Limit theorems for exponential random graphs
- Cut norm discontinuity of triangular truncation of graphons
- Breaking of ensemble equivalence for dense random graphs under a single constraint
- Large deviations for mean field model in Erdős-Rényi graph
- Upper tail of the spectral radius of sparse Erdös-Rényi graphs
- Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime
- The large deviation principle for interacting dynamical systems on random graphs
- A counterexample to the DeMarco-Kahn upper tail conjecture
- 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 tail bounds for stars
- Exceptional rotations of random graphs: a VC theory
- Lower tails via relative entropy
- Regular graphs with many triangles are structured
- Vertex order in some large constrained random graphs
- Rare events in random matrix theory
- The upper tail problem for induced 4‐cycles in sparse random graphs
- Exponential Chebyshev inequalities for random graphons and their applications
- Large deviation principle for the greedy exploration algorithm over Erdős-Rényi graphs
- A strong law of large numbers for random biased connected graphs
- The number of triangles in random intersection graphs
- A local central limit theorem for triangles in a random graph
- On the lower tail variational problem for random graphs
- Large deviations for random graphs. École d'Été de Probabilités de Saint-Flour XLV -- 2015
- On replica symmetry of large deviations in random graphs
- The large deviation principle for inhomogeneous Erdős-Rényi random graphs
- On the upper tail problem for random hypergraphs
- Asymptotic structure of constrained exponential random graph models
- Matrix estimation by universal singular value thresholding
- The lower tail: Poisson approximation revisited
- Reciprocity in directed networks
- A large deviation principle for the Erdős-Rényi uniform random graph
- On large deviation properties of Erdős-Rényi random graphs
- The role of topology in large deviations
- Large deviations of subgraph counts for sparse Erdős-Rényi graphs
- The missing log in large deviations for triangle counts
- Large-deviation properties of largest component for random graphs
- Title not available (Why is that?)
- A sample-path large deviation principle for dynamic Erdős-Rényi random graphs
- Bernoulli random matrices
- Moderate deviations via cumulants
- Differential calculus on graphon space
- Ensemble equivalence for dense graphs
- 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
- Exponential random graphs behave like mixtures of stochastic block models
- On the asymptotics of constrained exponential random graphs
- Discrete Malliavin-Stein method: Berry-Esseen bounds for random graphs and percolation
- Upper tail for homomorphism counts in constrained sparse 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
- Monochromatic subgraphs in randomly colored graphons
- Ground states for exponential random graphs
- On the phase transition curve in a directed exponential random graph model
- An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions
- A detailed investigation into near degenerate exponential random graphs
- Nonlinear large deviations: beyond the hypercube
- Ergodic theory on stationary random graphs
- Upper tails and independence polynomials in random graphs
- Dynamic Erdős-Rényi graphs
- Deviation probabilities for arithmetic progressions and other regular discrete structures
- Large deviation principles for empirical measures of colored random graphs
- 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
- Estimating and understanding exponential random graph models
- Right-convergence of sparse random graphs
- Rare Event Simulation Using Reversible Shaking Transformations
- An introduction to large deviations for random graphs
- The phases of large networks with edge and triangle constraints
- Chebyshev-type inequalities and large deviation principles
- Upper tails for arithmetic progressions in random subsets
- On string graph limits and the structure of a typical string graph
- The importance sampling technique for understanding rare events in Erdős-Rényi random graphs
- Emergent structures in large networks
- Rare event asymptotics for exploration processes for random graphs
- Asymptotic structure and singularities in constrained directed graphs
- Phase transitions in edge-weighted exponential random graphs: near-degeneracy and universality
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)
