Moderate deviations of subgraph counts in the Erdős-Rényi random graphs G(n,m) and G(n,p)

DOI10.1090/TRAN/8117zbMATH Open1443.05172arXiv1902.06830OpenAlexW3013031631MaRDI QIDQ3298973FDOQ3298973

Authors: Christina Goldschmidt, Simon Griffiths, Alex Scott 

Publication date: 17 July 2020

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Abstract: The main contribution of this article is an asymptotic expression for the rate associated with moderate deviations of subgraph counts in the ErdH{o}s-R'enyi random graph $G(n,m)$. Our approach is based on applying Freedman's inequalities for the probability of deviations of martingales to a martingale representation of subgraph count deviations. In addition, we prove that subgraph count deviations of different subgraphs are all linked, via the deviations of two specific graphs, the path of length two and the triangle. We also deduce new bounds for the related $G(n,p)$ model.

Full work available at URL: https://arxiv.org/abs/1902.06830

Recommendations

• Moderate deviations in a random graph and for the spectrum of Bernoulli random matrices
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• Moderate deviations in cycle count
• Moderate deviation in colored random graphs
• Subgraph counts in random graphs using incomplete U-statistics methods

zbMATH Keywords

moderate deviationsubgraph counts

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Martingales with discrete parameter (60G42) Enumeration in graph theory (05C30)

Cites Work

• On tail probabilities for martingales
• Probability Inequalities for Sums of Bounded Random Variables
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random graphs.
• When are small subgraphs of a random graph normally distributed?
• Weighted sums of certain dependent random variables
• Title not available (Why is that?)
• Moderate deviations via cumulants
• Asymptotic enumeration by degree sequence of graphs of high degree
• On the variational problem for upper tails in sparse random graphs
• The large deviation principle for the Erdős-Rényi random graph
• Degree sequences of random graphs
• A central limit theorem for decomposable random variables with applications to random graphs
• The infamous upper tail
• Moderate deviations in a random graph and for the spectrum of Bernoulli random matrices
• Orthogonal decompositions and functional limit theorems for random graph statistics
• A large deviation principle for the Erdős-Rényi uniform random graph
• An introduction to large deviations for random graphs
• The asymptotic distributions of generalized U-statistics with applications to random graphs
• On Littlewood's estimate for the binomial distribution
• On the probability in the tail of a binomial distribution
• A functional limit theorem for random graphs with applications to subgraph count statistics
• On the method of typical bounded differences
• Mod-\(\Phi\) convergence. Normality zones and precise deviations
• The lower tail: Poisson approximation revisited
• On the Choice Number of Random Hypergraphs
• Enumeration of graphs with a heavy-tailed degree sequence
• Some Approximations to the Binomial Distribution Function
• Random subgraph counts and U-statistics: multivariate normal approximation via exchangeable pairs and embedding
• Discrete Malliavin-Stein method: Berry-Esseen bounds for random graphs and percolation
• On the lower tail variational problem for random graphs

Cited In (9)

• Upper tails via high moments and entropic stability
• Deviation probabilities for arithmetic progressions and irregular discrete structures
• Moderate deviation in colored random graphs
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• Deviation probabilities for arithmetic progressions and other regular discrete structures
• Exponential inequalities for the number of subgraphs in the Erdös-Rényi random graph
• Moderate deviations in cycle count
• Moderate deviations in a random graph and for the spectrum of Bernoulli random matrices
• Title not available (Why is that?)

This page was built for publication: Moderate deviations of subgraph counts in the Erdős-Rényi random graphs \(G(n,m)\) and \(G(n,p)\)

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