Ramsey-goodness -- and otherwise

Peter Allen, Graham Brightwell, Jozef Skokan

Published 2010-10-25Version 1

A celebrated result of Chv\'atal, R\"odl, Szemer\'edi 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\"odl and Ruci\'nski 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\leq (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)\leq\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$.