BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Planar graphs: One graph to rule them all - Marthe Bonamy (Univers
 ity of Bordeaux)
DTSTART:20191024T133000Z
DTEND:20191024T143000Z
UID:TALK126343@talks.cam.ac.uk
CONTACT:Andrew Thomason
DESCRIPTION:Consider all planar graphs on n vertices. What is the smallest
  graph that contains them all as induced subgraphs? We provide an explicit
  construction of such a graph on n<sup>(4/3+o(1))</sup> vertices\, which i
 mproves upon the previous best upper bound of n<sup>(2+o(1))</sup>\, obtai
 ned in 2007 by Gavoille and Labourel.\n\nIn this talk\, we will gently int
 roduce the audience to the notion of so-called universal graphs (graphs co
 ntaining all graphs of a given family as induced subgraphs)\, and devote s
 ome time to a key lemma in the proof. That lemma comes from a recent break
 through by Dujmović\, Joret\, Micek\, Morin\, Ueckerdt and Wood regarding
  the structure of planar graphs\, and has already many interesting\nconseq
 uences - we hope the audience will be able to derive more. This is based o
 n joint work with Cyril Gavoille and Michal Pilipczuk.\n
LOCATION:MR12
END:VEVENT
END:VCALENDAR