Spring 2016

Recent Advances in Counting Sparse Graphs

Monday, May 2, 2016 2:45 pm3:30 pm PDT

Add to Calendar


Calvin Lab

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.