Title:

The upper tail problem for irregular graphs
Abstract:

For any graph H we let X_H denote the random variable counting the number of (unlabeled) copies of H in G_{n,p}.
The study of this random variable goes way back to the early works of Erdos and Renyi and its typical deviations are well understood. In this talk, we will discuss large deviations of X_H. In particular, we will be interested in the upper tail problem, that is – what is the probability of X_H > (1+delta) E[X_H]?
The upper tail problem proved to be very difficult, and even when H is the triangle, it was completely solved only recently by a breakthrough due to Harel, Mousset and Samotij. More generally, they gave almost optimal bounds when H is a non-bipartite regular graph. Building on this breakthrough, Basak and Basu obtained optimal bounds for any regular graph H.
In this talk we will discuss the difficulties of using this method in the case of irregular graphs. We will show how to overcome these issues for a certain range of p and improve the state-of-the-art result of Cook, Dembo, and Pham for almost all graphs.
The talk will be based on a joint work with Matan Harel, Frank Mousset and Wojciech Samotij.