BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Graphs with forbidden induced subgraphs - Alex Scott (University o
 f Oxford)
DTSTART:20200206T143000Z
DTEND:20200206T153000Z
UID:TALK138622@talks.cam.ac.uk
CONTACT:Andrew Thomason
DESCRIPTION:Ramsey's Theorem tells us that every graph on n vertices conta
 ins a complete subgraph or independent set of size about log n.  Consideri
 ng random graphs shows that this is all we can expect: for most graphs\, t
 he largest complete subgraph or independent set has size O(log n).  But wh
 at if we consider graphs G that do not contain some specific induced subgr
 aph H?  Erdos and Hajnal\nconjectured in the 1980s that in this case G mus
 t have a complete subgraph or independent set of size at least |G|^c\, for
  some c=c(H).  The Erdos-Hajnal conjecture remains open\, but we will disc
 uss some recent progress and related results.  This talk includes joint wo
 rk with Maria Chudnovsky\, Jacob Fox\, Paul Seymour and Sophie Spirkl.\n\n
LOCATION:MR12
END:VEVENT
END:VCALENDAR