Remarks on a Ramsey theory for trees

DOI10.1007/S00493-012-2763-3zbMATH Open1289.05452arXiv1107.5301OpenAlexW2006563044MaRDI QIDQ2392039FDOQ2392039

Authors: János Pach, József Solymosi, Gábor Tardos 

Publication date: 6 August 2013

Published in: Combinatorica (Search for Journal in Brave)

Abstract: Extending Furstenberg's ergodic theoretic proof for Szemer'edi's theorem on arithmetic progressions, Furstenberg and Weiss (2003) proved the following qualitative result. For every d and k, there exists an integer N such that no matter how we color the vertices of a complete binary tree T_N of depth N with k colors, we can find a monochromatic replica of T_d in T_N such that (1) all vertices at the same level in T_d are mapped into vertices at the same level in T_N; (2) if a vertex x of T_d is mapped into a vertex y in T_N, then the two children of x are mapped into descendants of the the two children of y in T_N, respectively; and 3 the levels occupied by this replica form an arithmetic progression. This result and its density versions imply van der Waerden's and Szemer'edi's theorems, and laid the foundations of a new Ramsey theory for trees. Using simple counting arguments and a randomized coloring algorithm called random split, we prove the following related result. Let N=N(d,k) denote the smallest positive integer such that no matter how we color the vertices of a complete binary tree T_N of depth N with k colors, we can find a monochromatic replica of T_d in T_N which satisfies properties (1) and (2) above. Then we have N(d,k)=Theta(dklog k). We also prove a density version of this result, which, combined with Szemer'edi's theorem, provides a very short combinatorial proof of a quantitative version of the Furstenberg-Weiss theorem.

Full work available at URL: https://arxiv.org/abs/1107.5301

Recommendations

• Upper bounds for a Ramsey theorem for trees
• The size-Ramsey number of trees
• An upper bound on the Ramsey number of trees

zbMATH Keywords

colorings of treesrandomized coloring algorithmreplica of a binary tree

Mathematics Subject Classification ID

Trees (05C05) Randomized algorithms (68W20) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Ramsey theory (05D10) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Ergodic behavior of diagonal measures and a theorem of Szemeredi on arithmetic progressions
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Polynomial extensions of van der Waerden’s and Szemerédi’s theorems
• A new proof of Szemerédi's theorem
• A density version of the Hales-Jewett theorem
• Title not available (Why is that?)
• On Some Sequences of Integers
• Markov Processes and Ramsey Theory for Trees
• Set-polynomials and polynomial extension of the Hales-Jewett theorem

Cited In (8)

• Local and mean Ramsey numbers for trees
• Direct and inverse results for popular differences in trees of positive dimension
• Measurable events indexed by products of trees
• Combinatorial Structures on van der Waerden sets
• Upper bounds for a Ramsey theorem for trees
• A density version of the Carlson-Simpson theorem
• A Ramseyian theorem on products of trees
• Arithmetic subtrees in large subsets of products of trees

This page was built for publication: Remarks on a Ramsey theory for trees

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