Dec 1, 3:30pm, Wean 8220

David Gamarnik, MIT

Interpolation method and scaling limits in sparse random graphs

David Gamarnik, MIT

Interpolation method and scaling limits in sparse random graphs

Abstract:

We will discuss existence of scaling limits in random graphs of
the following flavor:
given a sparse random graph, what is the limiting value of the largest cut
as the size of the graph diverges to infinity?
How many independent sets does a random graph have in the limit?

We will discuss the interpolation method as a powerful approach for proving the existence of such scaling limits and connections of these questions with the emerging field of graph limits. Finally, we will discuss applications of the interpolation method to Talagrand's conjecture regarding the limiting volume of a set generated by intersecting random subsets of a Euclidean space. Using the interpolation method we give a partial resolution of this conjecture.