Large deviations for triangles in random graphs in the critical regime

Zoom Link

A classic problem in probability theory and combinatorics is to estimate the probability that the random graph G(n,p) contains no triangles.  This problem can be viewed as a question in "non-linear large deviations".   The asymptotics of the logarithm of this probability (and related lower tail probabilities) are known in two distinct regimes.  When p>> 1/\sqrt{n}, at this level of accuracy the probability matches that of G(n,p) being bipartite; and when p<< 1/\sqrt{n}, Janson's Inequality gives the asymptotics of the log.  I will discuss a new approach to estimating this probability in the "critical regime": when p = \Theta(1/\sqrt{n}).  The approach uses ideas from statistical physics and algorithms and gives information about the typical structure of graphs drawn from the corresponding conditional distribution.  Based on joint work with Matthew Jenssen, Aditya Potukuchi, and Michael Simkin.  

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.