Combinatorics Colloquium: The upper tail for triangles in random graphs
- Event Type
- Seminar/Symposium
- Sponsor
- n/a
- Location
- Altgeld Hall (room # TBD)
- Date
- May 18, 2022 11:00 am
- Speaker
- Wojciech Samotij, Tel Aviv University
- Contact
- Jozsef Balogh
- jobal@illinois.edu
- Views
- 47
Abstract: Let $X$ denote the number of triangles in the random graph $G_{n,p}$. The problem of determining the asymptotics of the logarithimic upper tail probability of $X$, that is, $\log \Pr(X > (1+\delta)\mathbb{E}[X])$, for every fixed positive $\delta$ has attracted considerable attention of both the combinatorics and the probability communities. We shall present an elementary solution to this problem, obtained recently in a joint work with Matan Harel and Frank Mousset. The crux of our approach is a simple probabilistic argument, inspired by the work of Janson, Oleszkiewicz and Ruci\’nski, that reduces the estimation of this upper tail probability to a counting problem