![Counting Complexity and Phase Transitions_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Counting%20Complexity%20and%20Phase%20Transitions_hi-res.jpg?h=bf33d09a&itok=MrH5eN5T)
Abstract
I will discuss some recent breakthroughs in the probability literature on the problem of counting sparse graphs with prescribed properties, such as containing more than a given number of triangles. For dense graphs, such counting is possible using Szemeredi's lemma, but this tool is not available for sparse graphs. A new technique, called nonlinear large deviation theory, was introduced two years ago and has led to the resolutions of several open questions of this type. I will talk about the central aspects of this theory, some applications, the inadequacies of the theory in its current form and possibilities for further developments.