Tiling transitive tournaments and their blow-ups

Abstract

Let $T{T}_k$ denote the transitive tournament on $k$ vertices. Let $TT(h,k)$ denote the graph obtained from $T{T}_k$ by replacing each vertex with an independent set of size $h\ge 1$. The following result is proved: Let $c_2=1/2$, $c_3=5/6$ and $c_k=1-2^{-k-\log k}$ for $k\ge 4$. For every $\epsilon >0$ there exists $N=N(\epsilon ,h,k)$ such that for every undirected graph $G$ with $n>N$ vertices and with $\delta (G)\ge c_{k}n$, every orientation of $G$ contains vertex disjoint copies of $TT(h,k)$ that cover all but at most $\epsilon n$ vertices. In the cases $k=2$ and $k=3$ the result is asymptotically tight. For $k\ge 4$, $c_k$ cannot be improved to less than $1-2^{-0.5k(1+o(1))}$.

13 pages