Ramsey numbers for trees of small maximum degree (Q1848150)

The authors find upper bounds on the Ramsey number of trees, that have close connections to Burr's conjecture. The Ramsey number \(R(G,G)\) of a graph \(G\) is the smallest integer \(n\), such that any graph on \(n\) vertices contains the graph \(G\) or its complement. For a tree \(T\), which is bipartite of course, let the sizes of its color classes be \(t_1\) and \(t_2\), such that \(t_1 \leq t_2\). It is easy to see that \(R(T,T) \geq \max \{2t_1+t_2,2t_2\}-1\), and \textit{S. A. Burr} [Lect. Notes Math. 406, 52--75 (1974; Zbl 0293.05122)] conjectured that the equality is false; see \textit{J. W. Grossmann, F. Harary} and \textit{M. Klawe} [Discrete Math. 28, 247--254 (1979; Zbl 0434.05052)]. Now the authors show an almost matching upper bound for some classes of trees. The main theorem is as follows. Let \(\eta > 0\) be given. Then there exist \(N=N(\eta)\) and \(\delta=\delta(\eta)\) such that the following holds. For every \(t_1 \leq t_2 \in Z\) with \(t_2 \geq N\), and every tree \(T\) with maximum degree \(\Delta(T) \leq \delta t_2\) holds R\((T,T) \leq (1+\eta) \max \{2t_1+t_2,2t_2\}\). The proof is based on Szemerédi's celebrated regularity lemma.