Problems in Ramsey theory

在这个建议中，我将提到两个未来的研究方向，我希望与我未来的博士生一起追求。这两个方向都符合拉姆齐理论。Ramsey的经典定理（1930）断言，只要一个完全图G的N个顶点上的边是红-蓝的，就可以找到一个给定图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