Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653176 | European Journal of Combinatorics | 2017 | 9 Pages |
Abstract
Given positive integers hh and kk, denote by r(h,k)r(h,k) the smallest integer nn such that in any kk-coloring of the edges of a tournament on more than nn vertices there is a monochromatic copy of every oriented tree on hh vertices. We prove that r(h,k)=(h−1)kr(h,k)=(h−1)k for all kk sufficiently large (k=Θ(hlogh)k=Θ(hlogh) suffices). The bound (h−1)k(h−1)k is tight. The related parameter r∗(h,k)r∗(h,k) where some color contains all oriented trees is asymptotically determined. Values of r(h,2)r(h,2) for some small hh are also established.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Raphael Yuster,