The classical lower-tail problem for triangles in random graphs asks the following: given $\eta\in[0,1)$, what is the probability that $G(n,p)$ contains at most $\eta$ times the expected number of triangles? When $p=o(n^{-1/2})$ or $p = \omega(n^{-1/2})$ the asymptotics of the logarithm of this probability are known via Janson's inequality in the former case and regularity or container methods in the latter case.
We prove for the first time asymptotic formulas for the logarithm of the lower tail probability when $p=c n^{-1/2}$ for $c$ constant. Our results apply for all $c$ when $\eta \ge 1/2$ and for $c$ small enough when $\eta < 1/2$. For the special case $\eta=0$ of triangle-freeness, our results prove that a phase transition occurs as $c$ varies (in the sense of a non-analyticity of the rate function), while for $\eta \ge 1/2$ we prove that no phase transition occurs.
Our method involves ingredients from algorithms and statistical physics including rapid mixing of Markov chains and the cluster expansion. We complement our asymptotic formulas with efficient algorithms to approximately sample from $G(n,p)$ conditioned on the lower tail event.
Joint work with Will Perkins, Aditya Potukuchi and Michael Simkin.