Moderate deviations of subgraph counts in the Erdős-Rényi random graphs G(n,m) and G(n,p)
From MaRDI portal
Publication:3298973
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 . 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 model.
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
Cites work
- scientific article; zbMATH DE number 4170917 (Why is no real title available?)
- scientific article; zbMATH DE number 1246230 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- A central limit theorem for decomposable random variables with applications to random graphs
- A functional limit theorem for random graphs with applications to subgraph count statistics
- A large deviation principle for the Erdős-Rényi uniform random graph
- An introduction to large deviations for random graphs
- Asymptotic enumeration by degree sequence of graphs of high degree
- Degree sequences of random graphs
- Discrete Malliavin-Stein method: Berry-Esseen bounds for random graphs and percolation
- Enumeration of graphs with a heavy-tailed degree sequence
- Mod-\(\Phi\) convergence. Normality zones and precise deviations
- Moderate deviations in a random graph and for the spectrum of Bernoulli random matrices
- Moderate deviations via cumulants
- On Littlewood's estimate for the binomial distribution
- On tail probabilities for martingales
- On the Choice Number of Random Hypergraphs
- On the lower tail variational problem for random graphs
- On the method of typical bounded differences
- On the probability in the tail of a binomial distribution
- On the variational problem for upper tails in sparse random graphs
- Orthogonal decompositions and functional limit theorems for random graph statistics
- Probability Inequalities for Sums of Bounded Random Variables
- Random graphs.
- Random subgraph counts and U-statistics: multivariate normal approximation via exchangeable pairs and embedding
- Some Approximations to the Binomial Distribution Function
- The asymptotic distributions of generalized U-statistics with applications to random graphs
- The infamous upper tail
- The large deviation principle for the Erdős-Rényi random graph
- The lower tail: Poisson approximation revisited
- Weighted sums of certain dependent random variables
- When are small subgraphs of a random graph normally distributed?
Cited in
(9)- Moderate deviation in colored random graphs
- scientific article; zbMATH DE number 6011074 (Why is no real title available?)
- Large deviations of subgraph counts for sparse Erdős-Rényi graphs
- Upper tails via high moments and entropic stability
- Deviation probabilities for arithmetic progressions and irregular discrete structures
- Exponential inequalities for the number of subgraphs in the Erdös-Rényi random graph
- Moderate deviations in cycle count
- Deviation probabilities for arithmetic progressions and other regular discrete structures
- Moderate deviations in a random graph and for the spectrum of Bernoulli random matrices
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)
