BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Amalgamation - Dr Paul Russell (University of Cambridge)
DTSTART:20190426T180000Z
DTEND:20190426T190000Z
UID:TALK123646@talks.cam.ac.uk
CONTACT:Valentin Hübner
DESCRIPTION:Paul Erdős proved that there exist graphs with no short cycle
 s requiring \narbitrary many colours to colour their vertices so that no t
 wo adjacent \nvertices have the same colour. Unfortunately\, the proof doe
 s not explicitly \nconstruct such graphs. A well known example sheet probl
 em asks for an \nexample in the simplest case\, where we ban triangles--cy
 cles of length 3. \nSuch examples seem hard to find\, and tend to contain 
 many cycles of length \n4. I shall discuss a solution to this problem by N
 esetril and Rodl using \ntheir method of "amalgamation" which\, while it i
 s more complicated than \nother solutions\, also allows us to ban longer c
 ycles (and can do much more \nbesides). No prior knowledge of graph theory
  is required.
LOCATION:MR2\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR