Abstract

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<sup>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</sup>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.