Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime
Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime
复制标题
DOI：
10.1002/cpa.22036
复制
发表时间：
2019-12
影响因子：
3
通讯作者：
Anirban Basak;Riddhipratim Basu
中科院分区：
文献类型：
--
作者：
Anirban Basak;Riddhipratim Basu
对于 Δ 正则连通图 H，确定 Gn,p（具有边缘概率 p 的 n 个顶点上的 Erdős-Rényi 图）中 H 的副本数量的上尾大偏差的问题引起了人们的极大兴趣。对于 p<1 和 npΔ/2>>logn1/vH−2 ，其中 vH 是 H 中的顶点数，上尾大偏差事件被认为是由于局部结构的存在而发生的。在这种情况下，Gn,p 中 H 的副本数量超出预期一个常数因子的大偏差事件预计将以 n2pΔlog1/p 的速度保持，并且推测速率函数由平均场变分问题的解给出。经过近年来的一系列发展，逐渐覆盖更广泛的 p 范围，Harel、Mousset 和 Samotij 在整个局部政权中证明了固定大小的派系的上尾大偏差。本文建立了全局部域中所有连通正则图的猜想。 © 2021 Wiley 期刊有限责任公司。
For a Δ ‐regular connected graph H the problem of determining the upper tail large deviation for the number of copies of H in Gn,p , an Erdős‐Rényi graph on n vertices with edge probability p, has generated significant interest. For p≪1 and npΔ/2≫logn1/vH−2 , where vH is the number of vertices in H, the upper tail large deviation event is believed to occur due to the presence of localized structures. In this regime the large deviation event that the number of copies of H in Gn,p exceeds its expectation by a constant factor is predicted to hold at a speed n2pΔlog1/p , and the rate function is conjectured to be given by the solution of a mean‐field variational problem. After a series of developments in recent years, covering progressively broader ranges of p, the upper tail large deviations for cliques of fixed size were proved by Harel, Mousset, and Samotij in the entire localized regime. This paper establishes the conjecture for all connected regular graphs in the whole localized regime. © 2021 Wiley Periodicals LLC.