skip to content

Graph limits and entropy

Presented by: 
Svante Janson Uppsala Universitet
Wednesday 13th July 2016 - 11:00 to 11:45
INI Seminar Room 1
The entropy of a graph limit, or a graphon, was essentially defined by Aldous (although in a different, equivalent formulation), who showed that if a graph limit W has entropy H, then the entropy of the distribution of the corresponding random graph G(n,W) is asymptotically n^2 H/2.

Consider a hereditary class of graphs Q. Then the number of graphs of order n in Q is asymptotically given by exp( n^2 H/2), where H is the maximum entropy of a graph limit that is a limit of graphs in Q. Moreover, if this entropy maximizing limit is unique, then a uniformly random graph of order n in Q converges in probability, as n tends to infinity, to this maximizing graph limit.

As an example, we discuss the entropy maximising graph limits for the class of string graphs.

This is based on joint works with Hamed Hatami and Balasz Szegedy, and with Andrew Uzzel.

[ The video of this talk is temporarily unavailable. Please try later. ]

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons