Remarks on a Ramsey theory for trees

DOI10.1007/S00493-012-2763-3MaRDI QIDQ2392039zbMATH OpenOpenAlexFDO

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

Publication date 6 August 2013

Published in Combinatorica (Search for Journal in Brave)

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

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)

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.

Recommendations

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

Cites work

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

Cited in

(8)

• Local and mean Ramsey numbers for trees
• Measurable events indexed by products of trees
• Direct and inverse results for popular differences in trees of positive dimension
• 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)