A Completion of the Proof of the Edge-statistics Conjecture
Advances in Combinatronics (2020)
Voir la notice de l'article provenant de la source Advances in Combinatronics website
For given integers $k$ and $\ell$ with $0\ell {k \choose 2}$, Alon, Hefetz,
Krivelevich and Tyomkyn formulated the following conjecture: When sampling a
$k$-vertex subset uniformly at random from a very large graph $G$, then the
probability to have exactly $\ell$ edges within the sampled $k$-vertex subset
is at most $e^{-1}+o_k(1)$. This conjecture was proved in the case
$\Omega(k)\leq \ell\leq {k \choose 2}-\Omega(k)$ by Kwan, Sudakov and Tran. In
this paper, we complete the proof of the conjecture by resolving the remaining
cases. We furthermore give nearly tight upper bounds for the probability
described above in the case $\omega(1)\leq \ell\leq o(k)$. We also extend some
of our results to hypergraphs with bounded edge size.
Publié le :
@article{ADVC_2020_a8,
author = {Jacob Fox and Lisa Sauermann},
title = {A {Completion} of the {Proof} of the {Edge-statistics} {Conjecture}},
journal = {Advances in Combinatronics},
publisher = {mathdoc},
year = {2020},
language = {en},
url = {http://geodesic.mathdoc.fr/item/ADVC_2020_a8/}
}
Jacob Fox; Lisa Sauermann. A Completion of the Proof of the Edge-statistics Conjecture. Advances in Combinatronics (2020). http://geodesic.mathdoc.fr/item/ADVC_2020_a8/