Upper tails via high moments and entropic stability
Upper tails via high moments and entropic stability
复制标题
DOI：
10.1215/00127094-2021-0067
复制
发表时间：
2019-04
影响因子：
2.5
通讯作者：
Matan Harel;Frank Mousset;Wojciech Samotij
中科院分区：
文献类型：
--
作者：
Matan Harel;Frank Mousset;Wojciech Samotij
假设X是p-偏置离散超立方体上的非负系数有界次数多项式。我们的主要结果给出了尖锐的估计对数上尾概率$X$时，相关的极值问题满足一定的熵稳定性。我们应用这个结果解决了概率组合学中两个长期存在的问题：整数p-随机子集中固定长度算术级数个数的上尾问题和随机图G n，p中固定大小团个数的上尾问题.在固定正则图H在G_{n，p}$中的拷贝数的上尾问题上，我们也取得了显著的进展。为了满足有兴趣学习基本方法的读者，我们包含了一个简短的，自包含的解决方案，以解决$G_{n，p}$中三角形数量的上尾问题，对于所有$p=p（n）$满足$n^{-1}\log n\ll p \ll 1$。
Suppose that $X$ is a bounded-degree polynomial with nonnegative coefficients on the $p$-biased discrete hypercube. Our main result gives sharp estimates on the logarithmic upper tail probability of $X$ whenever an associated extremal problem satisfies a certain entropic stability property. We apply this result to solve two long-standing open problems in probabilistic combinatorics: the upper tail problem for the number of arithmetic progressions of a fixed length in the $p$-random subset of the integers and the upper tail problem for the number of cliques of a fixed size in the random graph $G_{n,p}$. We also make significant progress on the upper tail problem for the number of copies of a fixed regular graph $H$ in $G_{n,p}$. To accommodate readers who are interested in learning the basic method, we include a short, self-contained solution to the upper tail problem for the number of triangles in $G_{n,p}$ for all $p=p(n)$ satisfying $n^{-1}\log n\ll p \ll 1$.