On graphs with linear Ramsey numbers

For a fixed graph H, the Ramsey number r(H) is defined to be the least integer N such that in any 2-coloring of the edges of the complete graph KN, some monochromatic copy of H is always formed. Let ℋ︁(n, Δ) denote the class of graphs H having n vertices and maximum degree at most Δ. It was shown by Chvatál, Rödl, Szemerédi, and Trotter that for each Δ there exists c(Δ) such that r(H) < c(Δ)n for all H ϵ ℋ︁(n, Δ). That is, the Ramsey numbers grow linearly with the size of H. However, their proof relied on the well-known regularity lemma of Szemerédi and only gave an upper bound for c(Δ) which grew like an exponential tower of 2′ s of height Δ. This was remedied substantially in a recent paper of Eaton, who showed that one could take c(Δ) < 2 for some fixed c. Eaton, however, also used a variant of the regularity lemma in her proof. In this paper, we avoid the use of the regularity lemma altogether, and show that one can in fact take, for some fixed c, c(Δ) < 2 in the general case, and even c(Δ) < 2cΔ log Δ if H is bipartite. In particular, we improve an old upper bound on the Ramsey number of the n-cube due to Beck. We also show that for a fixed c′ > 0, and for all n and Δ, there are graphs H′ ϵ ℋ︁ (n, Δ) with r(H′) > 2c′Δn, which is not so far from our upper bound. In addition, we indicate how the upper bound result can be extended to the larger class of so-called p-arrangeable graphs, introduced by Chen and Schelp.