Upper tails and independence polynomials in random graphs

Abstract

The upper tail problem in the Erdős--Rényi random graph $G\sim {\mathcal{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+\delta$. Chatterjee and Dembo showed that in the sparse regime of $p\to 0$ as $n\to \infty$ with $p\ge n^{-\alpha }$ for an explicit $\alpha ={\alpha }_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(\delta )$ such that, for $p$ as above and any fixed $\delta >0$, the upper tail probability is $\exp [-(c_H(\delta )+o(1))n^2{p}^{\Delta }\log (1/p)]$, where $\Delta$ is the maximum degree of $H$. As it turns out, the leading order constant in the large deviation rate function, $c_H(\delta )$, is governed by the independence polynomial of $H$, defined as $P_H(x)=\sum 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(\delta )$ is the minimum between $\frac{1}{2}{\delta }^{2/m}$ and the unique positive solution of $P_H(x)=1+\delta$.

References in corpus (1)

• Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations

Cited by in corpus (14)

• Nonlinear large deviation bounds with applications to traces of Wigner matrices and cycles counts in Erdös-Renyi graphs
• Upper tails for arithmetic progressions in a random set
• Gaussian width bounds with applications to arithmetic progressions in random settings
• A counterexample to the DeMarco-Kahn Upper Tail Conjecture
• Upper tail bounds for Stars
• Large Deviations of Non-Stochastic Interacting Particles on Sparse Random Graphs
• Nonlinear Large Deviations: Beyond the Hypercube
• Large deviations for the largest eigenvalue of Gaussian networks with constant average degree
• A large deviation principle for block models
• Upper Tails of Subgraph Counts in Sparse Regular Graphs
• Preferential Attachment When Stable
• 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
• $PC$-polynomial of graph