Ramsey number of trees versus other graphs

拉姆齐树数与其他图的比较

• 批准号: 2606229
• 金额: --
• 依托单位: University of Warwick
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2021
• 资助国家: 英国
• 起止时间: 2021 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2606229
• 关键词: Ramsey; number; trees; versus; other

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.

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