Article ID Journal Published Year Pages File Type
4653176 European Journal of Combinatorics 2017 9 Pages PDF
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
,