Problems in Ramsey theory

点击翻译按钮获取中文摘要

In this proposal I will mention two future research directions that I hope to pursue together with my future Phd student. Both directions are in Ramsey theory. Ramsey's classical theorem (1930) asserts that whenever the edges of a complete graph G on N vertices are red-blue coloured, one can find a monochromatic (namely, all-red or all-blue) copy of a given graph H, provided that N is sufficiently large with respect to H. An interesting direction of research explores the structure of graphs G whose every red-blue colouring contains a monochromatic copy of H, and which are *minimal* with respect to this property. In particular, one could explore how small the minimum degree of such G could be. While a lot is known about this problem, there are many interesting open questions. Another direction with quite a different flavour explores the number of monochromatic copies of H in a red-blue coloured complete graph G. More specifically, one could ask for the maximum number of edge-disjoint monochromatic copies of H. Together with Gruslys, we have recently answered this question for the case where H is a triangle. Many variants of this question are open, yet some may be approachable with our techniques.Research Area: Logic and combinatorics