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) 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) Randomized algorithms (68W20)

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.

Review text

The authors use a randomized coloring algorithm, called random split, to prove two quantitative versions of Furstenberg-Weiss results from [\textit{H.~Furstenberg} and \textit{B.~Weiss}, Comb. Probab. Comput. 12, No. 5--6, 547--563 (2003; Zbl 1061.05094)]. Theorem: Let \(d\), \(n\) be positive integers, and let \(H\) be a subset of the vertex set of the vertex set of the binary tree \(T_n\) satisfying \[ 2^{w(H)}> \sum_{i=0}^{d-1}{n \choose i}. \] Then \(H\) contains a replica of \(T_d\). Here \(w(H) = \sum_{x\in H}w(x)\), \(w(x) = 2^{-l(x)}\), \(l(x)\) is the level of \(x\) in \(T_n\). Theorem: Let \(k,d,n \geqslant 2\) be integers. (i) Suppose that \(n > 5dk \log k\). Then, for any coloring of the vertices of \(T_n\) with \(k\) colors, one can find in \(T_n\) a monochromatic replica of \(T_d\). (ii) If \(n\leqslant (d-1)k\log (k/6)\), then there exists a coloring of \(T_n\) with \(k\) colors such that contains no monochromatic replica of \(T_d\).

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

• 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
• scientific article; zbMATH DE number 3523693 (Why is no real title available?)
• scientific article; zbMATH DE number 3323559 (Why is no real title available?)
• 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)

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

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)