Upper tail bounds for cycles

DOI10.1137/19M1258827MaRDI QIDQ5130906zbMATH OpenFDO

Authors 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

large deviationsrandom graphssubgraph countsupper tails

Mathematics Subject Classification ID

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

Abstract: This paper examines bounds on upper tails for cycle counts in $G_{n,p}$. For a fixed graph $H$ define $x{i}_H=x{i}_H^{n,p}$ to be the number of copies of $H$ in $G_{n,p}$. It is a much studied and surprisingly difficult problem to understand the upper tail of the distribution of $x{i}_H$, for example, to estimate �egin{equation*} mathbb{P}(xi_H > 2 mathbb{E}xi_H). end{equation*} The best known result for general $H$ and $p$ is due to Janson, Oleszkiewicz, and Ruci'nski, who, in 2004, proved �egin{align}label{a:JOR} exp[-O_{H, eta}(M_H(n,p) ln(1/p))]&<mathbb{P}(xi_H > (1+eta)mathbb{E} xi_H)\&<exp[-Omega_{H, eta}(M_{H}(n,p))]. onumber end{align} Thus they determined the upper tail up to a factor of $ln(1/p)$ in the exponent. There has since been substantial work to improve these bounds for particular $H$ and $p$. We close the $ln(1/p)$ gap for cycles, up to a constant in the exponent. Here the lower bound given by JOR is the truth for $l$-cycles when $p>fracl{n}^{1/(l-2)}nn$.

Recommendations

• Upper tails for subgraph counts in random graphs
• Upper tails via high moments and entropic stability
• Upper tails for triangles
• Tight upper tail bounds for cliques
• On the upper tail of counts of strictly balanced subgraphs

Cites work

• A large deviation result on the number of small subgraphs of a random graph
• Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order
• Concentration of multivariate polynomials and its applications
• Divide and conquer martingales and the number of triangles in a random graph
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 4000052 (Why is no real title available?)
• Inequalities with applications to percolation and reliability
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• Nonlinear large deviations
• On the missing log in upper tail estimates
• On the upper tail of counts of strictly balanced subgraphs
• On the variational problem for upper tails in sparse random graphs
• Poisson approximation for large deviations
• Proof of the Van den Berg–Kesten Conjecture
• Some intersection theorems for ordered sets and graphs
• The infamous upper tail
• The missing log in large deviations for triangle counts
• The probabilistic method
• Tight upper tail bounds for cliques
• Upper tail bounds for stars
• Upper tails for subgraph counts in random graphs
• Upper tails for triangles

Cited in

(4)

• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• The upper tail problem for induced 4‐cycles in sparse random graphs
• Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime
• Exponential inequalities for the tail probabilities of the number of cycles in generalized random graphs

This page was built for publication: Upper tail bounds for cycles

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