A Ramsey type result for oriented trees. (February 2017)

• Record Type: Journal Article
• Authors: Yuster, Raphael
• Is Part Of: European journal of combinatorics. Volume 60(2017)
• Page Start: 1
• Page End: 9
• Publication Date: 2017-02
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2016.08.010
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: Given positive integers h and k, denote by r ( h, k ) the smallest integer n such that in any k -coloring of the edges of a tournament on more than n vertices there is a monochromatic copy of every oriented tree on h vertices. We prove that r ( h, k ) = ( h − 1 ) k for all k sufficiently large ( k = Θ ( h log h ) suffices). The bound ( h − 1 ) k is tight. The related parameter r ∗ ( h, k ) where some color contains all oriented trees is asymptotically determined. Values of r ( h, 2 ) for some small h are also established.