The large deviation principle for the Erdős-Rényi random graph
From MaRDI portal
(Redirected from Publication:648962)
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
- 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
- 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?)
- 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)- Reciprocity in directed networks
- On the large deviations of traces of random matrices
- Exponential random graphs behave like mixtures of stochastic block models
- Upper tails for arithmetic progressions in random subsets
- 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
- A large deviation principle for the Erdős-Rényi uniform random graph
- Spectral edge in sparse random graphs: upper and lower tail large deviations
- Regular graphs with many triangles are structured
- Dynamic Erdős-Rényi 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
- The large deviation principle for interacting dynamical systems on random graphs
- Complex networks: structure and functionality
- Rare event asymptotics for exploration processes for random graphs
- Cut norm discontinuity of triangular truncation of graphons
- Upper tails via high moments and entropic stability
- Large deviation for uniform graphs with given degrees
- Replica symmetry in upper tails of mean-field hypergraphs
- Nonlinear large deviations: beyond the hypercube
- Large deviations of subgraph counts for sparse Erdős-Rényi graphs
- Phase transitions in finite random networks
- Exponential Chebyshev inequalities for random graphons and their applications
- Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs
- Approximating the cumulant generating function of triangles in the Erdös-Rényi random graph
- Matching polytons
- 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
- Upper tail bounds for stars
- Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits
- Monochromatic subgraphs in randomly colored graphons
- Matrix estimation by universal singular value thresholding
- Singularities in the entropy of asymptotically large simple graphs
- Differential calculus on graphon space
- Large deviations for random graphs. École d'Été de Probabilités de Saint-Flour XLV -- 2015
- 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
- Discrete Malliavin-Stein method: Berry-Esseen bounds for random graphs and percolation
- Estimating and understanding exponential random graph models
- Nonlinear large deviations
- On a question of Vera T. Sós about size forcing of graphons
- The lower tail: Poisson approximation revisited
- An introduction to large deviations for random graphs
- Emergent structures in large networks
- The missing log in large deviations for triangle counts
- On string graph limits and the structure of a typical string graph
- scientific article; zbMATH DE number 6011074 (Why is no real title available?)
- Ground states for exponential random graphs
- A detailed investigation into near degenerate exponential random graphs
- Vertex order in some large constrained random graphs
- On replica symmetry of large deviations in random graphs
- Perspectives on exponential random graphs
- Moderate deviations of subgraph counts in the Erdős-Rényi random graphs \(G(n,m)\) and \(G(n,p)\)
- Rare Event Simulation Using Reversible Shaking Transformations
- Moderate deviations via cumulants
- A principle of moderate deviations for the size of the largest component in an Erdős-Rényi random graph in the supercritical case
- Ergodic theory on stationary random graphs
- A strong law of large numbers for random biased connected graphs
- scientific article; zbMATH DE number 1943957 (Why is no real title available?)
- The phases of large networks with edge and triangle constraints
- Right-convergence of sparse random graphs
- On the asymptotics of constrained exponential random graphs
- Asymptotic structure and singularities in constrained directed graphs
- Large deviation principle for the greedy exploration algorithm over Erdős-Rényi graphs
- Chebyshev-type inequalities and large deviation principles
- Joint large deviation principle for some empirical measures of the d-regular random graphs
- The polytope of \(k\)-star densities
- Upper tails for edge eigenvalues of random graphs
- On the phase transition curve in a directed exponential random graph model
- A counterexample to the DeMarco-Kahn upper tail conjecture
- An L^p theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
- Asymptotic structure of graphs with the minimum number of triangles
- On the lower tail variational problem for random graphs
- scientific article; zbMATH DE number 5252621 (Why is no real title available?)
- On the variational problem for upper tails in sparse random graphs
- A local central limit theorem for triangles in a random graph
- Exceptional rotations of random graphs: a VC theory
- A large-deviations principle for all the components in a sparse inhomogeneous random graph
- 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
- scientific article; zbMATH DE number 7763253 (Why is no real title available?)
- Bernoulli random matrices
- Fluctuations of subgraph counts in graphon based random graphs
- Limits of multi-relational graphs
- Exponential inequalities for the number of subgraphs in the Erdös-Rényi random graph
- Lower tails via relative entropy
- Rare events in random matrix theory
- The upper tail problem for induced 4‐cycles in sparse random graphs
- Large-deviation properties of largest component for 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
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)
