Ramsey numbers for trees of small maximum degree

DOI10.1007/S004930200014MaRDI QIDQ1848150zbMATH OpenOpenAlexFDO

Authors Tomasz Łuczak, Penny Haxell, Peter Tingley

Publication date 3 November 2002

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004930200014

zbMATH Keywords

Burr's conjectureRamsey numbers of treesregularity lemma

Mathematics Subject Classification ID

Trees (05C05) Generalized Ramsey theory (05C55)

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.

Recommendations

• Ramsey numbers for trees with large maximum degree
• The size-Ramsey number of trees
• The size Ramsey number of trees with bounded degree
• scientific article; zbMATH DE number 4099362
• The Ramsey number of a graph with bounded maximum degree

Cited in

(16)

• A skew version of the Loebl-Komlós-Sós conjecture
• A version of the Loebl-Komlós-Sós conjecture for skew trees
• Ramsey numbers for bipartite graphs with small bandwidth
• The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs
• scientific article; zbMATH DE number 4099362 (Why is no real title available?)
• The size Ramsey number of trees with bounded degree
• Degree Ramsey numbers of closed blowups of trees
• Three-Color Bipartite Ramsey Number for Graphs with Small Bandwidth
• A note on the Size-Ramsey number of long subdivisions of graphs
• Ramsey numbers for trees with large maximum degree
• The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
• An approximate version of the Loebl-Komlós-Sós conjecture
• On the Ramsey number of the double star
• Degree Ramsey numbers for cycles and blowups of trees
• The Ramsey number of a graph with bounded maximum degree
• Loebl-Komlós-Sós conjecture: dense case

This page was built for publication: Ramsey numbers for trees of small maximum degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1848150)