On the upper tail problem for random hypergraphs
On the upper tail problem for random hypergraphs
复制标题
关于随机超图的上尾问题
DOI：
10.1002/rsa.20975
复制
发表时间：
2020
影响因子：
1
通讯作者：
Zhao, Yufei
中科院分区：
文献类型：
--
作者：
Liu, Yang P.;Zhao, Yufei
随机图的上尾问题要求估计ERDőS-Rényi随机图中某个固定子图的副本数超过其期望的某个常数因子的概率。在这个问题上，最近取得了许多令人兴奋的进展。我们研究了超图的相应问题，对超图的大偏差率知之甚少。我们提出了稀疏随机超图的上尾大偏差的新现象，这些现象在随机图中是不存在的。我们猜想了大偏差率的一个公式，即在稀疏的ErdőS-Rényi随机k-一致超图中，固定子图的拷贝数超出预期一个常数因子的对数概率的一阶渐近性。事实证明，与图表的情况相比，这个猜想要复杂得多。当被计数的固定子图是团时，以及当他的由八面体的交错面组成的3-均匀6点4边超图时，我们验证了我们的猜想，其中需要新的技术。
The upper tail problem in a random graph asks to estimate the probability that the number of copies of some fixed subgraph in an Erdős‐Rényi random graph exceeds its expectation by some constant factor. There has been much exciting recent progress on this problem. We study the corresponding problem for hypergraphs, for which less is known about the large deviation rate. We present new phenomena in upper tail large deviations for sparse random hypergraphs that are not seen in random graphs. We conjecture a formula for the large deviation rate, that is, the first order asymptotics of the log‐probability that the number of copies of fixed subgraphHin a sparse Erdős‐Rényi randomk‐uniform hypergraph exceeds its expectation by a constant factor. This conjecture turns out to be significantly more intricate compared to the case for graphs. We verify our conjecture when the fixed subgraphHbeing counted is a clique, as well as whenHis the 3‐uniform 6‐vertex 4‐edge hypergraph consisting of alternating faces of an octahedron, where new techniques are required.
登录
查看更多内容
影响因子：
2.2
作者：
Ronen Eldan
通讯作者：
Ronen Eldan
影响因子：
2.5
作者：
Matan Harel;Frank Mousset;Wojciech Samotij
通讯作者：
Matan Harel;Frank Mousset;Wojciech Samotij
影响因子：
3
作者：
Anirban Basak;Riddhipratim Basu
通讯作者：
Anirban Basak;Riddhipratim Basu
影响因子：
1.7
作者：
B. Bhattacharya;S. Ganguly;E. Lubetzky;Yufei Zhao
通讯作者：
Yufei Zhao
影响因子：
1
作者：
E. Lubetzky;Yufei Zhao
通讯作者：
E. Lubetzky;Yufei Zhao