Ramsey number of trees versus other graphs

图论中著名的Ramsey定理指出，对于任何有限图G和H，都存在一些N，使得在N个顶点上的完全图K_N的任何红/蓝染色要么包含G的红色副本，要么包含H的蓝色副本。这样的最小N称为G和H的Ramsey数，表示为G和H的Ramsey数。计算Ramsey数的精确值通常是非常困难的。事实上，在许多情况下，甚至很难提供良好的近似值。例如，尽管两个完全图的Ramsey数R(K_n，K_n)之间存在着很大的差距，但它们几十年来的下界2^{n/2}和上界4^n并没有得到有意义的改进。因此，Ramsey数的任何精确或良好的近似都是非常有意义的。在这个博士项目中，我将与我的导师Richard Montgomery以及他的博士后Matias Pavez-Signé一起工作，并在他们的指导下工作。其目的是证明关于形式R(T，H)的Ramsey数的各种精确结果，其中T是一棵树。除了利用该领域的许多标准工具，如Szemerédi的正则性引理、随机图方法和展开外，限制我们对树的关注还允许我们利用最近开发的几种树嵌入技术。其中之一是吸收法。粗略地说，这个想法是以一种聪明的方式保留图中的一小部分顶点，这样在将树的大部分嵌入到剩余的图中后，我们始终可以将保留的顶点吸收到这个嵌入中，以完成树的副本。这是我们特别感兴趣的，因为我们的目标是证明精确的结果，最近已经成功地使用吸收方法将这一领域的几个近似结果转化为精确的结果。第二种是Glebov，Johannsen和Krivelevich最近提出的一种逐点树嵌入方法，称为可扩充性方法。重新表述和提炼由Friedman和Pippenger最先提出的想法，以及Haxell后来的工作，他们的方法为嵌入几乎生成树提供了更灵活的框架。

The famous Ramsey's Theorem in Graph Theory states that for any finite graphs G and H, there exists some N such that any red/blue colouring of the complete graph K_N on N vertices either contains a red copy of G or a blue copy of H. The smallest such N, denoted by R(G,H) is called the Ramsey number of G and H. Computing the exact values of Ramsey numbers is generally very difficult. In fact, in many cases it is even hard to provide good approximations. As an example, the decades old lower bound of 2^{n/2} and upper bound of 4^n on the Ramsey number R(K_n,K_n) of two complete graphs have not been meaningfully improved, despite the large gap that exists between them. Therefore, any exact or good approximates of Ramsey numbers are of great interest. In this PhD project I will be working with and under the guidance of my supervisor Richard Montgomery, as well as his postdoc Matias Pavez-Signé. The goal is to prove various exact results on Ramsey numbers of the form R(T,H), where T is a tree. Aside from utilising many standard tools in the area, such as Szemerédi's Regularity Lemma, random graph methods and expansion, restricting our attention to trees also allows us to make use of a couple recently developed techniques for tree embeddings. One of these is the absorption method. Roughly speaking, the idea is to reserve a small proportion of vertices in the graph in a clever way, such that after embedding most of the tree into the remaining graph, we can always absorb the reserved vertices into this embedding to finish a copy of the tree. This is of particular interest to us as we are aiming to prove exact results and the absorption method have been successfully used lately to turn several approximate results in this area into exact ones. The second of these is a vertex-by-vertex tree embedding method called the extendibility method recently introduced by Glebov, Johannsen and Krivelevich. Reformulating and refining the ideas first proposed by Friedman and Pippenger, as well as later work by Haxell, their method provide a more flexible framework for embedding almost spanning trees.