## Abstract

The upper tail problem in the Erdős–Rényi random graph G∼G_{n,p} asks to estimate the probability that the number of copies of a graph H in G exceeds its expectation by a factor 1+δ. Chatterjee and Dembo showed that in the sparse regime of p→0 as n→∞ with p≥n^{−α} for an explicit α=α_{H}>0, this problem reduces to a natural variational problem on weighted graphs, which was thereafter asymptotically solved by two of the authors in the case where H is a clique. Here we extend the latter work to any fixed graph H and determine a function c_{H}(δ) such that, for p as above and any fixed δ>0, the upper tail probability is exp[−(c_{H}(δ)+o(1))n^{2}p^{Δ}log(1/p)], where Δ is the maximum degree of H. As it turns out, the leading order constant in the large deviation rate function, c_{H}(δ), is governed by the independence polynomial of H, defined as P_{H}(x)=∑i_{H}(k)x^{k} where i_{H}(k) is the number of independent sets of size k in H. For instance, if H is a regular graph on m vertices, then c_{H}(δ) is the minimum between [formula omitted] and the unique positive solution of P_{H}(x)=1+δ.

Original language | English (US) |
---|---|

Pages (from-to) | 313-347 |

Number of pages | 35 |

Journal | Advances in Mathematics |

Volume | 319 |

DOIs | |

State | Published - Oct 15 2017 |

## Keywords

- Large deviations
- Sparse random graphs
- Subgraph counts
- Upper tails
- Variational problems

## ASJC Scopus subject areas

- General Mathematics