Upper bounds for Ramsey numbers

The Ramsey number r(G) of a graph G is the smallest number n such that, in any two-colouring of the edges of the complete graph on n vertices, there is guaranteed to exist a monochromatic copy of G. In this thesis, we study the size of r(G) for a number of different types of graph G, proving several new upper bounds. Our main result is an improvement upon the upper bound for the most classical case of Ramsey’s theorem, finding the Ramsey number of the complete graph Kk. We also look at the closely related question of how many K­ks a two-colouring of a large Kn must contain, obtaining several interesting new results. After a brief discussion of bipartite Ramsey numbers we move on to our other main results, dealing with Ramsey numbers of sparse graphs. We prove, in particular, that a bipartite graph G with n vertices and maximum degree Δ has Ramsey number at most 2cΔn. Because of a construction of Graham, Rödl and Ruciński, we know that this result is, up to the constant c, best possible. We show, moreover, how to extend the method to hypergraphs in order to obtain a new proof of the sparse hypergraph Ramsey theorem: if H is a hypergraph with n vertices and maximum degree Δ the Ramsey number of H is at most c(Δ)n for some constant c(Δ) depending only on Δ. Note that these results were obtained simultaneously and independently by Jacob Fox and Benny Sudakov.EThOS - Electronic Theses Online ServiceGBUnited Kingdo