Talk information

Date: Sunday, December 22, 2024
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Michael Simkin (MIT)
Title: Lower tails for triangles inside the critical window

Abstract:

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 \ll 1/\sqrt{n}$ or $p \gg 1/\sqrt{n}$ 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/\sqrt{n}$, with $c$ fixed, with the large deviation event having at most $\eta$ times the expected number of triangles, for a fixed $\eta \in [0,1)$.

We prove explicit formula for the log-asymptotics of the event in question, for a wide range of pairs $(c,\eta)$. In particular, we show that for sufficiently small $\eta$ (including the triangle-free case $\eta=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 $\eta > 1/2$, then there is no phase transition.

As corollaries, we obtain analogous results for the $G(n;m)$ model, when $m = Cn^{3/2}$. In contrast to the $G(n;p)$ case, we show that a phase transition occurs as $C$ increases for all $\eta$.

Finally, we show that the probability of $G(n;m)$ being triangle-free, where $m=Cn^{3/2}$ for a sufficiently small constant $C$, conforms to a Poisson heuristic.

Joint with Matthew Jenssen, Will Perkins, and Aditya Potukuchi. Based on arXiv:2410.22951 and arXiv:2411.18563.