Mathematics – Combinatorics
Scientific paper
2011-07-26
Mathematics
Combinatorics
10 pages 1 figure
Scientific paper
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(dk\log 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.
pach János
Solymosi József
Tardos Gabor
No associations
LandOfFree
Remarks for the Ramsey theory for trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Remarks for the Ramsey theory for trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Remarks for the Ramsey theory for trees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-94505