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

DOI10.1002/rsa.10113zbMath1041.60042OpenAlexW2128405006MaRDI QIDQ4459588

Jeong Han Kim, Van H. 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

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

Related Items

Upper tails for subgraph counts in random graphs, Stein's method for concentration inequalities, Nonlinear large deviations, The missing log in large deviations for triangle counts, Upper tails for triangles, On replica symmetry of large deviations in random graphs, Upper tails via high moments and entropic stability, Upper tails and independence polynomials in random graphs, Concentration and consistency results for canonical and curved exponential-family models of random graphs, Applications of Stein's method for concentration inequalities, Upper tail for homomorphism counts in constrained sparse random graphs, Exponential inequalities for the number of subgraphs in the Erdös-Rényi random graph, Nonlinear large deviations: beyond the hypercube, The upper tail problem for induced 4‐cycles in sparse random graphs, Colorful triangle counting and a \textsc{MapReduce} implementation, Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime, Large deviations of subgraph counts for sparse Erdős-Rényi graphs, On the Method of Typical Bounded Differences, Unnamed Item, Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs, Upper Tail Bounds for Cycles, Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order, On the variational problem for upper tails in sparse random graphs, Moment inequalities for functions of independent random variables, Sub-Gaussian Tails for the Number of Triangles inG(n, p), Limit laws for the number of triangles in the generalized random graphs with random node weights, An introduction to large deviations for random graphs, Regular graphs with many triangles are structured, The C_ℓ‐free process, A concentration result with application to subgraph count, Rate of Convergence to the Poisson Law of the Numbers of Cycles in the Generalized Random Graphs, Tight upper tail bounds for cliques

Cites Work

• Upper tails for subgraph counts in random graphs