
arXiv: 1502.00867
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$\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 < δ < 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.
Extremal problems in graph theory, Large deviations, subgraph counts in a random graph, Probability (math.PR), Random graphs (graph-theoretic aspects), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics - Probability, lower tail large deviation problem
Extremal problems in graph theory, Large deviations, subgraph counts in a random graph, Probability (math.PR), Random graphs (graph-theoretic aspects), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics - Probability, lower tail large deviation problem
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 14 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
