Upper tails via high moments and entropic stability (Q2165741): Difference between revisions

This paper studies upper tail probability related to a bounded-degree polynomial with nonnegative coefficients on the \(p\)-based discrete hypercube. Let \(\Delta\ge 2\) be an integer and \(H\) be a connected non-bipartite and \(\Delta\)-regular graph. Suppose \(X\) is the number of copies of \(H\) in the random graph model \(G_{n,p}\). Let \(v_H\) be the number of vertices in \(H\). For every fixed \(\delta>0\) and \(p=p(n)\) satisfying \(n^{-1}(\ln n)^{\Delta v^2_H}\ll p^{\Delta/2}\ll 1\), it is shown that \(\lim_{n\rightarrow\infty}-\ln P(X\ge(1+\delta)EX)/(n^2p^{\Delta}\ln(1/p))=\delta^{2/v_H}/2\) if \(np^{\Delta}\rightarrow0\) and \(\min\{\delta^{2/v_H}/2,\theta\}\) if \(np^{\Delta}\rightarrow\infty\), where \(\theta\) is the unique positive solution to \(P_H(\theta)=1+\delta\). Here, \(P_H(\theta)=\sum_k i_k(H)\theta^k\), where \(i_k(H)\) is the number of independent sets of \(H\) of size \(k\). If \(H\) is a connected \(\Delta\)-regular graph, then for \(n^{-1}\ll p^{\Delta/2}\ll n^{-1}(\ln n)^{1/v_H^{-2}}\), it is shown that \(\lim_{n\rightarrow\infty}-\ln P(X\ge(1+\delta)EX)/EX=(1+\delta)\ln (1+\delta)-\delta\). Based on the developed techniques, cliques in random graphs and extensions to regular graphs have also be considered.