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