Combinatorics: Wojciech Samotij (TAU)

Title: The lower tail for triangles in random graphs


Let $X$ denote the number of triangles in the random graph $G_{n,p}$. The problem of determining the asymptotics of the logarithmic lower tail probability of~$X$, that is, the function $f_c(n,p) = - \log \Pr(X \le c \Ex[X])$, for $c \in [0,1)$, has attracted considerable attention of both the combinatorics and the probability communities. In this talk, we explain how one can bound $f_c(n,p)$ from above by solving a natural combinatorial optimisation problem that generalises Mantel's / Tur\'an's theorem. Moreover, we will prove a matching lower bound on $f_c(n,p)$ in the case $p = 1/2$. Our argument, which employs ideas from an earlier joint work with Gady Kozma, Tom Meyerovitch, and Ron Peled, exploits connections between entropy and independence.

This is joint work with Gady Kozma.


Mon, 20/01/2020 - 10:00 to 12:00


C-400, CS building