Divide and conquer martingales and the number of triangles in a random graph

DOI10.1002/RSA.10113MaRDI QIDQ4459588zbMATH OpenOpenAlexFDO

Authors Jeong Han Kim, Van Vu

Publication date 29 March 2004

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.10113

Mathematics Subject Classification ID

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

Recommendations

• A large deviation result on the number of small subgraphs of a random graph
• scientific article; zbMATH DE number 18981
• scientific article; zbMATH DE number 1195776
• A concentration inequality for maximum matching size in random graphs¹
• Upper tails for triangles

Cites work

• Upper tails for subgraph counts in random graphs

Cited in

(33)

• Upper tails for subgraph counts in random graphs
• Upper tails via high moments and entropic stability
• On replica symmetry of large deviations in random graphs
• The symmetry in the martingale inequality
• Limit laws for the number of triangles in the generalized random graphs with random node weights
• 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
• The missing log in large deviations for triangle counts
• Upper tails for triangles
• Tight upper tail bounds for cliques
• Upper tail for homomorphism counts in constrained sparse random graphs
• Concentration and consistency results for canonical and curved exponential-family models of random graphs
• A concentration result with application to subgraph count
• Nonlinear large deviations: beyond the hypercube
• Upper tails and independence polynomials in random graphs
• scientific article; zbMATH DE number 7763253 (Why is no real title available?)
• Moment inequalities for functions of independent random variables
• 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
• Sub-Gaussian tails for the number of triangles in \(G( n, p)\)
• 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
• The C_ℓ‐free process
• On the method of typical bounded differences
• Colorful triangle counting and a \textsc{MapReduce} implementation
• Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order
• Stein's method for concentration inequalities
• Regular graphs with many triangles are structured
• Applications of Stein's method for concentration inequalities
• Upper tail bounds for cycles
• Rate of convergence to the Poisson law of the numbers of cycles in the generalized random graphs
• The upper tail problem for induced 4‐cycles in sparse random graphs
• Nonlinear large deviations

This page was built for publication: Divide and conquer martingales and the number of triangles in a random graph

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