An edge-colored rooted directed tree (aka arborescence) is path-monochromatic if every path in it is monochromatic. Let be positive integers. For a tournament , let be the largest integer such that every -edge coloring of has a path-monochromatic subtree with at least vertices and let be the restriction to subtrees of depth at most . It was proved by Landau that and proved by Sands et al. that where . Here we consider and in more generality, determine their extremal values in most cases, and in fact in all cases assuming the Caccetta-Häggkvist Conjecture. We also study the typical value of and , i.e., when is a random tournament.

生成讲解博客的中文版本

生成AI智能校验的中文版本