Ramsey numbers of trees

Abstract

We show that there exists a constant $c>0$ such that every $n$-vertex tree $T$ with $\hat{I}”(T)\le cn$ has Ramsey number $R(T)=\max \{t_1+2t_2,2t_1\}-1$, where $t_1\ge t_2$ are the sizes of the bipartition classes of $T$. This improves an asymptotic result of Haxell, Łuczak, and Tingley from 2002, and shows that, though Burr's 1974 conjecture on the Ramsey numbers of trees has long been known to be false for certain `double stars', it is true for trees with up to small linear maximum degree.

59 pages, 22 figures