On two problems in graph Ramsey theory - Conlon, D; Fox, J; Sudakov, B (Springer Verlag, 2012)
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 KN contains a monochromatic copy of H. A famous result of Chváatal, 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 2c′Δ ≤ c(Δ) ≤ cΔlog2Δ. We improve this upper bound, showing that there is a constant c for which c(Δ) ≤ 2cΔlogΔ. The induced Ramsey number rind(H) of a graph H is the least positive integer N for which there exists a graph G on N vertices such that every two-coloring of the edges of G contains an induced monochromatic copy of H. Erdős conjectured the existence of a constant c such that, for any graph H on n vertices, rind(H) ≤ 2cn. We move a step closer to proving this conjecture, showing that rind(H) ≤ 2cnlogn. This improves upon an earlier result of Kohayakawa, Prömel and Rödl by a factor of logn in the exponent.