On the lower tail variational problem for random graphs

Abstract

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 Erdős-Rényi random graph $\mathcal{G}(n,p)$. We are interested in estimating the lower tail probability $\mathbb{P}(X_H\le (1-\delta )\mathbb{E}{X}_H)$ 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\ge 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\to 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-bipartite $H$ and $\delta$ close to 1.

15 pages, 5 figures, 1 table

References in corpus (3)

• An information theoretic approach to Sidorenko's conjecture
• On the logarithimic calculus and Sidorenko's conjecture
• Reciprocity in directed networks

Cited by in corpus (3)

• Upper tails for arithmetic progressions in a random set
• Moderate Deviations of Triangle Counts in the Erdős-Rényi Random Graph $G(n,m)$: The Lower Tail
• On the upper tail problem for random hypergraphs