Upper Tail Bounds for Cycles

DOI10.1137/19M1258827zbMath1450.05081arXiv1903.07488MaRDI QIDQ5130906

Abigail Raz

Publication date: 29 October 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

random graphslarge deviationssubgraph countsupper tails

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Large deviations (60F10) Approximations to statistical distributions (nonasymptotic) (62E17)

Related Items (2)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the upper tail of counts of strictly balanced subgraphs
• Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order
• Some intersection theorems for ordered sets and graphs
• Upper tails for subgraph counts in random graphs
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• On the missing log in upper tail estimates
• Upper tail bounds for stars
• Nonlinear large deviations
• On the Choice Number of Random Hypergraphs
• The missing log in large deviations for triangle counts
• Upper tails for triangles
• Tight upper tail bounds for cliques
• Inequalities with applications to percolation and reliability
• Poisson approximation for large deviations
• Divide and conquer martingales and the number of triangles in a random graph
• The infamous upper tail
• Proof of the Van den Berg–Kesten Conjecture
• On the variational problem for upper tails in sparse random graphs
• Concentration of multivariate polynomials and its applications

This page was built for publication: Upper Tail Bounds for Cycles