Abigail Raz

dblp:130/6973 · DBLP profile ↗
← Back
2ranked-venue papers
1as first author
1since 2021 · last 2023
0000-0003-2081-598XORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 1 first-author · 1 since 2021
YearPublicationVenuePosition
2023 The iterative independent model
Erin Meger, Abigail Raz
Discret. Appl. Math.2
2020 Upper Tail Bounds for Cycles
abstract
This paper examines bounds on upper tails for cycle counts in $G_{n,p}$. For a fixed graph $H$ define $\xi_H= \xi_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 $\xi_H$, for example, to estimate $\mathbb{P}(\xi_H > 2 \mathbb{E}\xi_H).$ The best known result for general $H$ and $p$ is due to Janson, Oleszkiewicz, and Ruciński [ Israel J. Math., 142 (2004), pp. 61--92], who proved that $ \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))]. $ 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 stated above is accurate for $l$-cycles when $p> \frac{\ln^{1/(l-2)}n}{n}$.
Abigail Raz
SIAM J. Discret. Math.1