The missing log in large deviations for triangle counts
From MaRDI portal
Abstract: This paper solves the problem of sharp large deviation estimates for the upper tail of the number of triangles in an Erdos-Renyi random graph, by establishing a logarithmic factor in the exponent that was missing till now. It is possible that the method of proof may extend to general subgraph counts.
Recommendations
Cites work
- A large deviation result on the number of small subgraphs of a random graph
- Applications of Stein's method for concentration inequalities
- Concentration inequalities using the entropy method
- Concentration of measure and isoperimetric inequalities in product spaces
- Concentration of multivariate polynomials and its applications
- Concentration of non‐Lipschitz functions and applications
- Divide and conquer martingales and the number of triangles in a random graph
- On the number of subgraphs of prescribed type of graphs with a given number of edges
- Poisson approximation for large deviations
- Probability Inequalities for Sums of Bounded Random Variables
- The deletion method for upper tail estimates
- The infamous upper tail
- The large deviation principle for the Erdős-Rényi random graph
- Threshold functions for small subgraphs
- Upper tails for subgraph counts in random graphs
- Upper tails for triangles
- When are small subgraphs of a random graph normally distributed?
Cited in
(38)- Concentration inequalities on the multislice and for sampling without replacement
- Upper tails via high moments and entropic stability
- Localization in random geometric graphs with too many edges
- On the lower tail variational problem for random graphs
- On replica symmetry of large deviations in random graphs
- A tail bound for read-k families of functions
- Modified log-Sobolev inequalities and two-level concentration
- Large deviations of the empirical spectral measure of supercritical sparse Wigner matrices
- On the upper tail problem for random hypergraphs
- Moderate deviations of triangle counts in sparse Erdős-Rényi random graphs G(n, m) and G(n, p)
- The lower tail: Poisson approximation revisited
- Large deviations of subgraph counts for sparse Erdős-Rényi graphs
- Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs
- Moderate deviations via cumulants
- Tight upper tail bounds for cliques
- Upper tail for homomorphism counts in constrained sparse random graphs
- Upper tails and independence polynomials in random graphs
- scientific article; zbMATH DE number 7763253 (Why is no real title available?)
- On the missing log in upper tail estimates
- A large deviation principle for block models
- Exponential inequalities for the number of subgraphs in the Erdös-Rényi random graph
- On the variational problem for upper tails in sparse random graphs
- Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime
- An introduction to large deviations for random graphs
- A counterexample to the DeMarco-Kahn upper tail conjecture
- Large deviations for the isoperimetric constant in 2D percolation
- Moderate deviations in cycle count
- Upper tails for arithmetic progressions in random subsets
- Upper tail bounds for stars
- The large deviation principle for the Erdős-Rényi random graph
- Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order
- Lower large deviations for geometric functionals
- Regular graphs with many triangles are structured
- Lower tails via relative entropy
- Upper tail bounds for cycles
- Large deviations in random latin squares
- The upper tail problem for induced 4‐cycles in sparse random graphs
- Nonlinear large deviations
This page was built for publication: The missing log in large deviations for triangle counts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904593)
