Tiling directed graphs with tournaments

Abstract

The Hajnal--Szemerédi theorem states that for any integer $r\ge 1$ and any multiple $n$ of $r$, if $G$ is a graph on $n$ vertices and $\delta (G)\ge (1-1/r)n$, then $G$ can be partitioned into $n/r$ vertex-disjoint copies of the complete graph on $r$ vertices. We prove a very general analogue of this result for directed graphs: for any integer $r\ge 4$ and any sufficiently large multiple $n$ of $r$, if $G$ is a directed graph on $n$ vertices and every vertex is incident to at least $2(1-1/r)n-1$ directed edges, then $G$ can be partitioned into $n/r$ vertex-disjoint subgraphs of size $r$ each of which contain every tournament on $r$ vertices. A related Turán-type result is also proven.

39 pages, 2 figures