The University College London (UCL) Combinatorics Seminar is held every Monday at 4–5pm during term time.

To subscribe to the mailing list, please email Luke Collins on luke [dot] collins [dot] 22 [at] ucl [dot] ac [dot] uk.

Next Speaker

• 28th April 2025 - Asaf Cohen (Tel Aviv University)

  On the upper tail problem for irregular graphs

  
  

  Venue: Drayton House, Jevons Lecture Theatre B20.

  For a graph $H$, 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 back to the early works of Erdős–Rényi and its typical deviations are well understood. In this talk, we will discuss the large deviations of $X_H$. In particular, we will be interested in the upper tail problem, that is—what is the upper tail probability of $H$, namely, $\Pr(X_H > (1+\delta)E[X_H])$?

  The upper tail problem proved to be very difficult, and even when $H$ is the triangle, the asymptotics of the logarithm of the upper tail probability, was solved only quite recently, by a breakthrough due to Harel, Mousset and Samotij. More generally, together with a follow up result of Basak and Basu, the asymptotic value of the logarithm of the upper tail probability was resolved for any regular graph $H$.

  Throughout the talk, first we will discuss the known results in the field, and the difficulties in extending their proofs for irregular graphs when $p$ is small. Then, we will present an improvement for the state of the art theorem of Cook, Dembo and Pham, by estimating the logarithm of the upper tail probability of any irregular graph $H$, for sparser values of $p$, some of which are optimal.

  The talk will be based on a joint work with Matan Harel, Frank Mousset and Wojciech Samotij.