The Ramsey number of dense graphs

Abstract

The Ramsey number r(H) of a graph H is the smallest number n such that, in any two-colouring of the edges of K_n, there is a monochromatic copy of H. We study the Ramsey number of graphs H with t vertices and density ρ, proving that r(H) ≤ 2^(c√(ρ)log(2/ρ)t). We also investigate some related problems, such as the Ramsey number of graphs with t vertices and maximum degree ρt and the Ramsey number of random graphs in G(t, ρ), that is, graphs on t vertices where each edge has been chosen independently with probability ρ.

Files

Additional details