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