BEGIN:VCALENDAR VERSION:2.0 PRODID:-//talks.cam.ac.uk//v3//EN BEGIN:VTIMEZONE TZID:Europe/London BEGIN:DAYLIGHT TZOFFSETFROM:+0000 TZOFFSETTO:+0100 TZNAME:BST DTSTART:19700329T010000 RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU END:DAYLIGHT BEGIN:STANDARD TZOFFSETFROM:+0100 TZOFFSETTO:+0000 TZNAME:GMT DTSTART:19701025T020000 RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU END:STANDARD END:VTIMEZONE BEGIN:VEVENT CATEGORIES:Isaac Newton Institute Seminar Series SUMMARY:Graph limits and entropy - Svante Janson (Uppsala Universitet) DTSTART;TZID=Europe/London:20160713T110000 DTEND;TZID=Europe/London:20160713T114500 UID:TALK66731AThttp://talks.cam.ac.uk URL:http://talks.cam.ac.uk/talk/index/66731 DESCRIPTION:The entropy of a graph limit\, or a graphon\, was essentially defined by Aldous (although in a diffe rent\, equivalent formulation)\, who showed that i f a graph limit W has entropy H\, then the entropy of the distribution of the corresponding random g raph G(n\,W) is asymptotically n^2 H/2.

Con sider a hereditary class of graphs Q. Then the num ber of graphs of order n in Q is asymptotically gi ven by exp( n^2 H/2)\, where H is the maximum entr opy 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 infi nity\, to this maximizing graph limit.

As a n example\, we discuss the entropy maximising grap h limits for the class of string graphs.

Th is is based on joint works with Hamed Hatami and B alasz Szegedy\, and with Andrew Uzzel.
LOCATION:Seminar Room 1\, Newton Institute CONTACT:info@newton.ac.uk END:VEVENT END:VCALENDAR