Path-monochromatic bounded depth rooted trees in (random) tournaments

An edge -colored rooted directed tree (aka arborescence) is path -monochromatic if every path in it is monochromatic. Let k, t be positive integers. For a tournament T , let f T ( k ) be the largest integer such that every k -edge coloring of T has a path -monochromatic subtree with at least f T ( k ) vertices and let f T ( k, t) be the restriction to subtrees of depth at most t . It was proved by Landau that f T ( 1 , 2 ) = n and proved by Sands et al. that f T ( 2 ) = n where | V ( T ) | = n . Here we consider f T ( k ) and f T ( k, t) in more generality, determine their extremal values in most cases, and in fact in all cases assuming the Caccetta-H & auml;ggkvist Conjecture. We also study the typical value of f T ( k ) and f T ( k, t) , i.e., when T is a random tournament. (c) 2024 Elsevier B.V. All rights reserved.