Ramsey number of trees versus other graphs

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

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.