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 K N , 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   2   c Δ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   c Δ(log Δ)   2in the general case, and even c (Δ) < 2 c Δ 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 ′) > 2 c ′ Δ 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. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 176–192, 2000