A concentration result with application to subgraph count

DOI10.1002/rsa.20371zbMath1236.05140arXiv0912.3868OpenAlexW1981989522MaRDI QIDQ3119051

Guy Wolfovitz

Publication date: 7 March 2012

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

Full work available at URL: https://arxiv.org/abs/0912.3868

zbMATH Keywords

random graphssubgraph countconcentration resultsub-Gaussian tail bounds

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65)

Related Items (3)

Upper tails for arithmetic progressions in random subsets ⋮ Hölder-type inequalities and their applications to concentration and correlation bounds ⋮ On the missing log in upper tail estimates

Cites Work

• When are small subgraphs of a random graph normally distributed?
• Upper tails for subgraph counts in random graphs
• Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs
• On the Choice Number of Random Hypergraphs
• Sub-Gaussian Tails for the Number of Triangles inG(n, p)
• Poisson approximation for large deviations
• Divide and conquer martingales and the number of triangles in a random graph
• On the concentration of multivariate polynomials with small expectation
• Concentration of non‐Lipschitz functions and applications
• The infamous upper tail

This page was built for publication: A concentration result with application to subgraph count