Ramsey-goodness -- and otherwise

Abstract

A celebrated result of Chvátal, Rödl, Szemerédi and Trotter states (in slightly weakened form) that, for every natural number $\Delta$, there is a constant $r_{\Delta }$ such that, for any connected $n$-vertex graph $G$ with maximum degree $\Delta$, the Ramsey number $R(G,G)$ is at most $r_{\Delta }n$, provided $n$ is sufficiently large. In 1987, Burr made a strong conjecture implying that one may take $r_{\Delta }=\Delta$. However, Graham, Rödl and Ruciński showed, by taking $G$ to be a suitable expander graph, that necessarily $r_{\Delta }>2^{c\Delta }$ for some constant $c>0$. We show that the use of expanders is essential: if we impose the additional restriction that the bandwidth of $G$ be at most some function $\beta (n)=o(n)$, then $R(G,G)\le (2\chi (G)+4)n\le (2\Delta +6)n$, i.e., $r_{\Delta }=2\Delta +6$ suffices. On the other hand, we show that Burr's conjecture itself fails even for $P_n^k$, the $k$th power of a path $P_n$. Brandt showed that for any $c$, if $\Delta$ is sufficiently large, there are connected $n$-vertex graphs $G$ with $\Delta (G)\le \Delta$ but $R(G,K_3)>cn$. We show that, given $\Delta$ and $H$, there are $\beta >0$ and $n_0$ such that, if $G$ is a connected graph on $n\ge n_0$ vertices with maximum degree at most $\Delta$ and bandwidth at most $\beta n$, then we have $R(G,H)=(\chi (H)-1)(n-1)+\sigma (H)$, where $\sigma (H)$ is the smallest size of any part in any $\chi (H)$-partition of $H$. We also show that the same conclusion holds without any restriction on the maximum degree of $G$ if the bandwidth of $G$ is at most $\epsilon (H)\log n/\log \log n$.

34 pages