Problems in Ramsey theory

在这份提案中，我将提到我希望与我未来的博士生一起追求的两个未来研究方向。这两个方向都在拉姆齐理论中。Ramsey的经典定理(1930)断言，只要N个顶点上的完全图G的边是红蓝色的，就可以找到给定图H的一个单色(即，全红或全蓝)副本，只要N相对于H足够大。一个有趣的研究方向探索了图G的结构，它的每个红蓝染色都包含H的单色副本，并且关于这一性质是*极小的。特别是，人们可以探索这种G的最小程度有多小。虽然对这个问题有很多了解，但也有许多有趣的悬而未决的问题。另一个具有完全不同风格的方向是探索红蓝色完全图G中H的单色拷贝数。更具体地说，人们可以问H的边不相交的单色拷贝的最大数目。最近，我们与Gruslys一起回答了H是三角形的情况。这个问题的许多变体都是开放的，但有些可能是我们的技术可以接近的。研究领域：逻辑和组合学

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