2024/11/27 by Matthew Jenssen, Jenssen, Matthew, Will Perkins +5 · 1 citation
Engineering · #Structural Analysis and Optimization
paper · pdf · doi:10.48550/arxiv.2411.18563
We study the probability that the random graph G(n,p) is triangle-free. When p =o(n-1/2) or p = ω(n-1/2) the asymptotics of the logarithm of this probability are known via Janson's inequality in the former case and via regularity or hypergraph container methods in the latter case. We prove for the first time an asymptotic formula for the logarithm of this probability when p = c n-1/2 for c a sufficiently small constant. More generally, we study lower-tail large deviations for triangles in random graphs: the probability that G(n,p) has at most η times its expected number of triangles, when p = c n-1/2 for c and η∈ [0,1) constant. Our results apply for all c if η≥ .4993 and for c small enough otherwise. For η small (including the case of triangle-freeness), we prove that a phase transition occurs as c varies, in the sense of a non-analyticity of the rate function, while for η≥ .4993 we prove that no phase transition occurs. On the other hand for the random graph G(n,m), with m = b n3/2, we show that a phase transition occurs in the lower-tail problem for triangles as b varies for every η∈ [0,1). Our method involves ingredients from algorithms and statistical physics including the cluster expansion and concentration inequalities for contractive Markov chains.