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

DOI10.1214/18-ECP181MaRDI QIDQ1990048zbMATH OpenOpenAlexFDO

Authors Amir Dembo, Eyal Lubetzky

Publication date 24 October 2018

Published in Electronic Communications in Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.11327, https://projecteuclid.org/euclid.ecp/1540346603

zbMATH Keywords

constrained random graphsErdős-Rényi graphslarge deviations

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Large deviations (60F10)

Abstract: Starting with the large deviation principle (LDP) for the ErdH{o}s-R'enyi binomial random graph $mathcalG(n,p)$ (edge indicators are i.i.d.), due to Chatterjee and Varadhan (2011), we derive the LDP for the uniform random graph $mathcalG(n,m)$ (the uniform distribution over graphs with $n$ vertices and $m$ edges), at suitable $m=m_n$. Applying the latter LDP we find that tail decays for subgraph counts in $mathcalG(n,m_n)$ are controlled by variational problems, which up to a constant shift, coincide with those studied by Kenyon et al. and Radin et al. in the context of constrained random graphs, e.g., the edge/triangle model.

Recommendations

• The large deviation principle for the Erdős-Rényi random graph
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• On the lower tail variational problem for random graphs
• 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

Cites work

• Bipodal structure in oversaturated random graphs
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Ensemble equivalence for dense graphs
• Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Large deviations techniques and applications.
• Large networks and graph limits
• Limits of dense graph sequences
• Multipodal structure and phase transitions in large constrained graphs
• Nonlinear large deviations
• On replica symmetry of large deviations in random graphs
• On the Distribution of the Number of Successes in Independent Trials
• On the lower tail variational problem for random graphs
• On the variational problem for upper tails in sparse random graphs
• Phase transitions in a complex network
• The large deviation principle for the Erdős-Rényi random graph
• The phases of large networks with edge and triangle constraints
• The probabilistic method
• Upper tails and independence polynomials in random graphs

Cited in

(22)

• 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
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• Exponential Chebyshev inequalities for random graphons and their applications
• Approximating the cumulant generating function of triangles in the Erdös-Rényi random graph
• Discrete Malliavin-Stein method: Berry-Esseen bounds for random graphs and percolation
• Moderate deviations of subgraph counts in the Erdős-Rényi random graphs \(G(n,m)\) and \(G(n,p)\)
• A strong law of large numbers for random biased connected graphs
• scientific article; zbMATH DE number 5252621 (Why is no real title available?)
• A large-deviations principle for all the components in a sparse inhomogeneous random graph
• Upper tail for homomorphism counts in constrained sparse random graphs
• Moderate deviations in cycle count
• 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
• Existence of a symmetric bipodal phase in the edge-triangle model
• The large deviation principle for the Erdős-Rényi random graph
• Optimal graphons in the edge-2star model
• Marked random graphs with given degree sequence: large deviations on the local topology and applications
• A large deviation principle for block models
• Large deviation principles for graphon sampling
• On large deviation properties of Erdős-Rényi random graphs

This page was built for publication: A large deviation principle for the Erdős-Rényi uniform random graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1990048)