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

DOI10.1002/RSA.10113zbMATH Open1041.60042OpenAlexW2128405006MaRDI QIDQ4459588FDOQ4459588

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

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

Mathematics Subject Classification ID

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

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
• Title not available (Why is that?)
• Upper tails and independence polynomials in random graphs
• 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
• Moment inequalities for functions of independent random variables
• Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime
• Sub-Gaussian tails for the number of triangles in \(G( n, p)\)
• The C_ℓ‐free process
• An introduction to large deviations for random graphs
• On the method of typical bounded differences
• Colorful triangle counting and a \textsc{MapReduce} implementation
• Stein's method for concentration inequalities
• Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order
• Regular graphs with many triangles are structured
• Upper tail bounds for cycles
• Applications of Stein's method for concentration inequalities
• 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)