On the Lower Tail Variational Problem for Random Graphs

We study the lower tail large deviation problem for subgraph counts in a random graph. LetXHdenote the number of copies ofHin an Erdős–Rényi random graph G(n,p) . We are interested in estimating the lower tail probability P(XH ≤ (1-δ) E XH) for fixed 0 < δ < 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 forp≥n−αH(and conjecturally for a larger range ofp). We study this variational problem and provide a partial characterization of the so-called ‘replica symmetric’ phase. Informally, our main result says that for everyH, and 0 < δ < δHfor some δH> 0, asp→ 0 slowly, the main contribution to the lower tail probability comes from Erdős–Rényi random graphs with a uniformly tilted edge density. On the other hand, this is false for non-bipartiteHand δ close to 1.