BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: We say a graph G is Ramsey for a graph H if every red/blue edg
 e-colouring of the edges of G contains a monochromatic copy of H. The size 
 Ramsey number of a graph H is defined to be the minimum number of edges amo
 ng all graphs which are Ramsey for H. The study of size Ramsey numbers orig
 inated by the work of Erdős\, Faudree\, Rousseau and Schelp from 1970's. Th
 is number was studied for graphs including paths\, cycles\, powers of paths
  and cycles\, trees of bounded degree. For all mentioned graphs it was show
 n that the size Ramsey number grows linearly in the number of vertices ("is
  linear"). This line of research was inspired by a question of Beck who ask
 ed whether the size Ramsey number is linear for graphs of bounded degree. L
 ater this was disproved by Rödl and Szemerédi. In this talk I will present 
 our recent result showing that fixed powers of bounded degree trees also ha
 ve linear size Ramsey number. Equivalently\, this result says that all grap
 hs of bounded degree and bounded treewidth have linear size Ramsey number. 
 We also obtain off-diagonal version of this result. Many exciting problems 
 remain open. This is joint work with Nina Kam\v{c}ev\, Anita Liebenau and D
 avid Wood. 
DTSTAMP:20191031T201000
DTSTART:20191104T160000
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9 
 \n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:Liana Yepremyan (University of Oxford): On the size Ramsey number o
 f bounded powers of bounded degree trees
UID:95691478@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20191104-C-Yepremyan.html
END:VEVENT
END:VCALENDAR