On two problems in graph Ramsey theory

Abstract

We study two classical problems in graph Ramsey theory, that of determining the Ramsey number of bounded-degree graphs and that of estimating the induced Ramsey number for a graph with a given number of vertices. The Ramsey number r(H) of a graph H is the least positive integer N such that every two-coloring of the edges of the complete graph K_N contains a monochromatic copy of H. A famous result of Chvátal, Rödl, Szemerédi and Trotter states that there exists a constant c(Δ) such that r(H) ≤ c(Δ)n for every graph H with n vertices and maximum degree Δ. The important open question is to determine the constant c(Δ). The best results, both due to Graham, Rödl and Ruciński, state that there are positive constants c and c' such that 2^(c'Δ) ≤ c(Δ) ≤ c^(Δlog^(2)Δ). We improve this upper bound, showing that there is a constant c for which c(Δ) ≤ 2^(cΔlogΔ).

Files

Additional details