Upper tails and independence polynomials in random graphs
Upper tails and independence polynomials in random graphs
复制标题
随机图中的上尾和独立多项式
DOI：
10.1016/j.aim.2017.08.003
复制
发表时间：
2015
影响因子：
1.7
通讯作者：
Yufei Zhao
中科院分区：
文献类型：
--
作者：
B. Bhattacharya;S. Ganguly;E. Lubetzky;Yufei Zhao
Erdős-Rényi 随机图 G∼ G n, p 中的上尾问题要求估计 G 中图 H 的副本数量超出预期 1+δ 倍的概率。 Chatterjee 和 Dembo 表明，在 p→ 0 的稀疏机制中，当 n→∞ 且 p≥ n− α 且显式 α= α H> 0 时，该问题简化为加权图上的自然变分问题，此后由两位作者在 H 为团的情况下渐近解决。这里，我们将后面的工作扩展到任何固定图 H 并确定一个函数 c H (δ)，使得对于上述 p 和任何固定 δ> 0，上尾概率为 exp[−(c H (δ)+ o (1)) n 2 p Δ log(1/p)]，其中 Δ 是 H 的最大次数。事实证明，大偏差率函数中的前导常数 c H (δ) 由独立多项式控制H 的，定义为 P H (x)=Σ i H (k) x k，其中 i H (k) 是 H 中大小为 k 的独立集合的数量。例如，如果 H 是 m 个顶点的正则图，则 c H (δ) 是 1 2 δ 2/m 和 P H (x)= 1+ δ 的唯一正解之间的最小值。
The upper tail problem in the Erdős–Rényi random graph G∼ G n, p asks to estimate the probability that the number of copies of a graph H in G exceeds its expectation by a factor 1+ δ. Chatterjee and Dembo showed that in the sparse regime of p→ 0 as n→∞ with p≥ n− α for an explicit α= α H> 0, this problem reduces to a natural variational problem on weighted graphs, which was thereafter asymptotically solved by two of the authors in the case where H is a clique. Here we extend the latter work to any fixed graph H and determine a function c H (δ) such that, for p as above and any fixed δ> 0, the upper tail probability is exp[−(c H (δ)+ o (1)) n 2 p Δ log(1/p)], where Δ is the maximum degree of H. As it turns out, the leading order constant in the large deviation rate function, c H (δ), is governed by the independence polynomial of H, defined as P H (x)=∑ i H (k) x k where i H (k) is the number of independent sets of size k in H. For instance, if H is a regular graph on m vertices, then c H (δ) is the minimum between 1 2 δ 2/m and the unique positive solution of P H (x)= 1+ δ.