Ramsey numbers of sparse graphs

Let d be a fixed natural number. There is a theorem, due to Chvátal, Rodl,

Szemerédi and Trotter (CRST), saying that the Ramsey number of any graph G

with maximum degree d and n vertices is at most c(d)n, that is it grows

linearly with the size of n. The original proof of this theorem uses the

regularity lemma and the resulting dependence of c on d is of tower-type.

This bound has been improved over the years to the stage where we are now

grappling with proving the correct dependency, believed to be an

exponential in d. Our first main result is a proof that this is indeed the

case if we assume additionally that G is bipartite, that is, for a

bipartite graph G with n vertices and maximum degree d, we have r(G)