- Series
- Graph Theory Seminar
- Time
- Tuesday, October 28, 2025 - 3:30pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Michael Simkin – MIT – https://math.mit.edu/~msimkin/
- Organizer
- Xiying Du and Rose McCarty
How likely is $G(n;p)$ to have a less-than-typical number of triangles? This is a foundational question in non-linear large deviation theory. When $p >> n^{-1/2}$ or $p >> n^{-1/2}$ the answer is fairly well-understood, with Janson's inequality applying in the former case and regularity- or container-based methods applying in the latter. We study the regime $p = c n^{-1/2}$, with $c>0$ fixed, with the large deviation event having at most $E$ times the expected number of triangles, for a fixed $0 <= E < 1$.
We prove explicit formula for the log-asymptotics of the event in question, for a wide range of pairs $(c,E)$. In particular, we show that for sufficiently small $E$ (including the triangle-free case $E = 0$) there is a phase transition as $c$ increases, in the sense of a non-analytic point in the rate function. On the other hand, if $E > 1/2$, then there is no phase transition.
As corollaries, we obtain analogous results for the $G(n;m)$ model, when $m = C n^{3/2}$. In contrast to the $G(n;p)$ case, we show that a phase transition occurs as $C$ increases for all $E$.
Finally, we show that the probability of $G(n;m)$ being triangle free, where $m = C n^{3/2}$ for a sufficiently small constant $C$, conforms to a Poisson heuristic.
Joint with Matthew Jenssen, Will Perkins, and Aditya Potukuchi.