Upper tails and independence polynomials in random graphs

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²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 [formula omitted] and the unique positive solution of P_H(x)=1+δ.