Upper tails and independence polynomials in random graphs

Here we extend the latter work to any fixed graph H and determine a function cH(δ) such that, for p as above and any fixed δ>0, the upper tail probability is exp⁡[−(cH(δ)+o(1))n2pΔlog⁡(1/p)], where Δ is the maximum degree of H. As it turns out, the leading order constant in the large deviation rate function, cH(δ), is governed by the independence polynomial of H, defined as PH(x)=∑iH(k)xk where iH(k) is the number of independent sets of size k in H. For instance, if H is a regular graph on m vertices, then cH(δ) is the minimum between 12δ2/m and the unique positive solution of PH(x)=1+δ.