On the Lower Tail Variational Problem for Random Graphs

We study the lower tail large deviation problem for subgraph counts in a random graph. Let X-H denote the number of copies of H in an Erdos-Renyi random graph G(n, p). We are interested in estimating the lower tail probability P(X-H <= (1 - delta)EXH) for fixed 0 < delta < 1. Thanks to the results of Chatterjee, Dembo and Varadhan, this large deviation problem has been reduced to a natural variational problem over graphons, at least for p >= n(-alpha H) (and conjecturally for a larger range of p). We study this variational problem and provide a partial characterization of the so-called 'replica symmetric' phase. Informally, our main result says that for every H, and 0 < delta < delta(H) for some delta(H) > 0, as p -> 0 slowly, the main contribution to the lower tail probability comes from Erdos-Renyi random graphs with a uniformly tilted edge density. On the other hand, this is false for non-bipartite H and delta close to 1.