Transitive partitions in realizations of tournament score sequences

A tournament is an oriented complete graph, and one containing no directed cycles is called transitive . A tournament T =( V, A ) is called m ‐ partition transitive if there is a partition \documentclass{article}\usepackage{amssymb} \usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty} \begin{document}${{V}}={{X}}_{{{1}}} {\cup\hskip-8.5pt{\cdot}\hskip4pt} {{X}}_{{{2}}} {\cup\hskip-8.5pt{\cdot}\hskip4pt} \ldots {\cup\hskip-8.5pt{\cdot}\hskip4pt}{{X}}_{{{m}}}$\end{document} such that the subtournaments induced by each X i are all transitive, and T is m ‐ partition k ‐ transitive if max| X i |= k . Two tournaments are equivalent if they have the same out‐degree sequence. We show that for any m and k , T is equivalent to an m ‐partition k ‐transitive tournament T ′ whenever T is equivalent to any tournament which contains a transitive subtournament of order at least k . This generalizes results of Guiduli et al. and Acosta et al., who proved the claim for m =2 and k =⌈ n /2⌉, and m >2 and k ⩽⌈ n /2⌉, respectively. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 52–62, 2010