Springe direkt zu Inhalt

Colloquium by Liana Yepremyan (University of Oxford): On the size Ramsey number of bounded powers of bounded degree trees

Nov 04, 2019 | 04:00 PM s.t.

We say a graph G is Ramsey for a graph H if every red/blue edge-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 among all graphs which are Ramsey for H. The study of size Ramsey numbers originated by the work of Erdős, Faudree, Rousseau and Schelp from 1970's. This number was studied for graphs including paths, cycles, powers of paths and cycles, trees of bounded degree. For all mentioned graphs it was shown 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 asked whether the size Ramsey number is linear for graphs of bounded degree. Later 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 have linear size Ramsey number. Equivalently, this result says that all graphs 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 David Wood.

Time & Location

Nov 04, 2019 | 04:00 PM s.t.

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
Room 005 (Ground Floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)