Ramsey numbers for trees of small maximum degree
type: Item
instance of: scholarly article
title: Ramsey numbers for trees of small maximum degree
zbMATH Open document ID: 0997.05065
author: Tomasz Łuczak
author: Penny Haxell
author: Peter Tingley
published in: Combinatorica
publication date: 2002-11-03T00:00:00Z
review text: 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.
reviewed by: András Pluhár
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1822338
zbMATH Keywords: Ramsey numbers of trees
zbMATH Keywords: Burr's conjecture
zbMATH Keywords: regularity lemma
MaRDI profile type: Publication
full work available at URL: s004930200014
OpenAlex ID: W2016667694
DOI: 10.1007/S004930200014
description: scientific article; zbMATH DE number 1822338