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:Combinatorics Seminar
SUMMARY:Planar graphs: One graph to rule them all - Marthe
Bonamy (University of Bordeaux)
DTSTART;TZID=Europe/London:20191024T143000
DTEND;TZID=Europe/London:20191024T153000
UID:TALK126343AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/126343
DESCRIPTION:Consider all planar graphs on n vertices. What is
the smallest graph that contains them all as induc
ed subgraphs? We provide an explicit construction
of such a graph on n(4/3+o(1)) vertices
\, which improves upon the previous best upper bou
nd of n(2+o(1))\, obtained in 2007 by G
avoille and Labourel.\n\nIn this talk\, we will ge
ntly introduce the audience to the notion of so-ca
lled universal graphs (graphs containing all graph
s of a given family as induced subgraphs)\, and de
vote some time to a key lemma in the proof. That l
emma comes from a recent breakthrough by Dujmović\
, Joret\, Micek\, Morin\, Ueckerdt and Wood regard
ing the structure of planar graphs\, and has alrea
dy many interesting\nconsequences - we hope the au
dience will be able to derive more. This is based
on joint work with Cyril Gavoille and Michal Pilip
czuk.\n
LOCATION:MR12
CONTACT:Andrew Thomason
END:VEVENT
END:VCALENDAR