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

DOI10.1016/j.ejc.2011.03.014zbMath1230.05259arXiv1008.1946OpenAlexW2041354341WikidataQ105583608 ScholiaQ105583608MaRDI QIDQ648962

Sourav Chatterjee, Srinivasa 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 lemma graph limits number of triangles double phase transition

Mathematics Subject Classification ID

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

Related Items

Complex networks: structure and functionality ⋮ Chebyshev-Type Inequalities and Large Deviation Principles ⋮ Reciprocity in directed networks ⋮ Rare Event Simulation Using Reversible Shaking Transformations ⋮ Rare event asymptotics for exploration processes for random graphs ⋮ Nonlinear large deviations ⋮ On the large deviations of traces of random matrices ⋮ Exponential random graphs behave like mixtures of stochastic block models ⋮ The missing log in large deviations for triangle counts ⋮ A detailed investigation into near degenerate exponential random graphs ⋮ Vertex Order in Some Large Constrained Random Graphs ⋮ Cut norm discontinuity of triangular truncation of graphons ⋮ On replica symmetry of large deviations in random graphs ⋮ Moderate deviations via cumulants ⋮ Upper tails via high moments and entropic stability ⋮ Large deviation for uniform graphs with given degrees ⋮ Upper tails and independence polynomials in random graphs ⋮ Asymptotic structure of constrained exponential random graph models ⋮ Multipodal structure and phase transitions in large constrained graphs ⋮ Upper tails for arithmetic progressions in random subsets ⋮ Replica symmetry in upper tails of mean-field hypergraphs ⋮ A large-deviations principle for all the components in a sparse inhomogeneous random graph ⋮ On a question of Vera T. Sós about size forcing of graphons ⋮ Upper tail of the spectral radius of sparse Erdös-Rényi graphs ⋮ On the upper tail problem for random hypergraphs ⋮ Upper tail for homomorphism counts in constrained sparse random graphs ⋮ A large‐deviations principle for all the cluster sizes of a sparse Erdős–Rényi graph ⋮ Deviation probabilities for arithmetic progressions and other regular discrete structures ⋮ Large deviations for subcomplex counts and Betti numbers in multiparameter simplicial complexes ⋮ Moderate deviations in cycle count ⋮ The number of triangles in random intersection graphs ⋮ Bernoulli random matrices ⋮ Fluctuations of subgraph counts in graphon based random graphs ⋮ Limits of multi-relational graphs ⋮ Upper Tails for Edge Eigenvalues of Random Graphs ⋮ Exponential inequalities for the number of subgraphs in the Erdös-Rényi random graph ⋮ Lower tails via relative entropy ⋮ Nonlinear large deviations: beyond the hypercube ⋮ The phases of large networks with edge and triangle constraints ⋮ Rare events in random matrix theory ⋮ The upper tail problem for induced 4‐cycles in sparse random graphs ⋮ Deviation probabilities for arithmetic progressions and irregular discrete structures ⋮ Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime ⋮ Large deviations of subgraph counts for sparse Erdős-Rényi graphs ⋮ Typical large graphs with given edge and triangle densities ⋮ The large deviation principle for inhomogeneous Erdős-Rényi random graphs ⋮ A sample-path large deviation principle for dynamic Erdős-Rényi random graphs ⋮ Breaking of ensemble equivalence for dense random graphs under a single constraint ⋮ Phase transitions in finite random networks ⋮ Exponential Chebyshev inequalities for random graphons and their applications ⋮ Asymptotic Structure of Graphs with the Minimum Number of Triangles ⋮ On the Lower Tail Variational Problem for Random Graphs ⋮ Estimating and understanding exponential random graph models ⋮ On String Graph Limits and the Structure of a Typical String Graph ⋮ Unnamed Item ⋮ Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs ⋮ Right-convergence of sparse random graphs ⋮ Mixing time of exponential random graphs ⋮ Perspectives on exponential random graphs ⋮ Approximating the cumulant generating function of triangles in the Erdös-Rényi random graph ⋮ Moderate deviations of subgraph counts in the Erdős-Rényi random graphs 𝐺(𝑛,𝑚) and 𝐺(𝑛,𝑝) ⋮ Asymptotic structure and singularities in constrained directed graphs ⋮ The polytope of \(k\)-star densities ⋮ A large deviation principle for the Erdős-Rényi uniform random graph ⋮ Ensemble equivalence for dense graphs ⋮ Phase transitions in edge-weighted exponential random graphs: near-degeneracy and universality ⋮ The role of topology in large deviations ⋮ Sparse maximum-entropy random graphs with a given power-law degree distribution ⋮ On the variational problem for upper tails in sparse random graphs ⋮ Matching polytons ⋮ On the asymptotics of constrained exponential random graphs ⋮ The lower tail: Poisson approximation revisited ⋮ Spectral edge in sparse random graphs: upper and lower tail large deviations ⋮ Degeneracy in sparse ERGMs with functions of degrees as sufficient statistics ⋮ On the phase transition curve in a directed exponential random graph model ⋮ A counterexample to the DeMarco‐Kahn upper tail conjecture ⋮ Large deviations of empirical neighborhood distribution in sparse random graphs ⋮ Limit laws for the number of triangles in the generalized random graphs with random node weights ⋮ An introduction to large deviations for random graphs ⋮ Upper tail bounds for stars ⋮ An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions ⋮ Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits ⋮ Regular graphs with many triangles are structured ⋮ Monochromatic subgraphs in randomly colored graphons ⋮ Emergent Structures in Large Networks ⋮ Matrix estimation by universal singular value thresholding ⋮ Singularities in the entropy of asymptotically large simple graphs ⋮ Large deviations for the largest eigenvalue of Gaussian networks with constant average degree ⋮ Large deviation principle for the maximal eigenvalue of inhomogeneous Erdős-Rényi random graphs ⋮ Ground states for exponential random graphs ⋮ Differential calculus on graphon space ⋮ The large deviation principle for interacting dynamical systems on random graphs

Cites Work