On the variational problem for upper tails in sparse random graphs
On the variational problem for upper tails in sparse random graphs
复制标题
DOI：
10.1002/rsa.20658
复制
发表时间：
2014-02
影响因子：
1
通讯作者：
E. Lubetzky;Yufei Zhao
中科院分区：
文献类型：
--
作者：
E. Lubetzky;Yufei Zhao
在边密度为p的Erdens-Rényi随机图Gn，p中，三角形的个数至少是其均值的两倍的概率是多少？将其写作exp[-r（n，p）]，当p = o（1）时，速率函数r（n，p）的阶数已经是一个长期存在的悬而未决的问题，最终由Chatterjee以及DeMarco和Kahn于2012年解决，他们独立证明了r（n，p）n2 p2 log（1/p）对于p lognn ; r（n，p）的精确渐进性仍然未知。下面的变分问题可以与这个在p lognn处的大偏差问题相关：对于δ > 0固定，三角形密度至少为（1 + δ）p3的n个顶点上的加权图的最小渐近p-相对熵是多少？Chatterjee和Varadhan（2011）的一个漂亮的大偏差框架将三角形的上尾简化为固定p的限制版本。Chatterjee和Dembo最近的一个突破将其有效性扩展到了显式α > 0的n−α <$p <$1，并且可能在上述所有稀疏区域都成立。
What is the probability that the number of triangles in Gn,p , the Erdős‐Rényi random graph with edge density p, is at least twice its mean? Writing it as exp[−r(n,p)] , already the order of the rate function r(n, p) was a longstanding open problem when p = o(1), finally settled in 2012 by Chatterjee and by DeMarco and Kahn, who independently showed that r(n,p)≍n2p2log(1/p) for p≳lognn ; the exact asymptotics of r(n, p) remained unknown. The following variational problem can be related to this large deviation question at p≳lognn : for δ > 0 fixed, what is the minimum asymptotic p‐relative entropy of a weighted graph on n vertices with triangle density at least (1 + δ)p3? A beautiful large deviation framework of Chatterjee and Varadhan (2011) reduces upper tails for triangles to a limiting version of this problem for fixed p. A very recent breakthrough of Chatterjee and Dembo extended its validity to n−α≪p≪1 for an explicit α > 0, and plausibly it holds in all of the above sparse regime.