Turán-type and tiling problems in oriented graphs

Abstract

Given $a,b,c\in \mathbb{N}$, let $D_{a,b,c}$ be the tournament on $a+b+c$ vertices obtained by replacing the vertices of the directed triangle $C_3$ with transitive tournaments $T{T}_a$, $T{T}_b$, and $T{T}_c$, respectively. Keevash and Sudakov (2009) showed that every sufficiently large oriented graph $G$ on $n$ vertices with $\hat{I}{´}^0(G)⩾(1/2-o(1))n$ contains a $C_3$-tiling, equivalently a $D_{1,1,1}$-tiling, covering all but at most three vertices. We generalize this result to arbitrary blow-ups $D_{a,b,c}$. Specifically, for any fixed $a,b,c$, every sufficiently large oriented graph $G$ on $n$ vertices with $\hat{I}{´}^0(G)⩾(1/2-o(1))n$ contains a $D_{a,b,c}$-tiling covering all but at most $2(a+b+c)-3$ vertices. Moreover, this bound is essentially sharp. We also establish a stronger stability result: if $(a+b+c)\mid n$, then either $G$ contains a $D_{a,b,c}$-factor, or $G$ is close to an extremal graph. Our interest in $D_{a,b,c}$ is also motivated by oriented Turán theory: a seminal theorem of Bollobás and Häggkvist (1990) shows that a tournament $T$ is Turánable (i.e., contained in every sufficiently large regular tournament) if and only if $T\subseteq D_{s,s,s}$ for some $s$. Complementing our tiling results, we also investigate related semi-degree thresholds for powers of directed cycles and paths. In particular, we present two $n$-vertex constructions that give lower bounds, showing that the minimum semi-degree thresholds for $C_l^2$ with $l\not\equiv 0(\mathrm{mod}6)$ and for $P_l^2$ with $l⩾7$ are at least $4n/9$ and $3n/8$, respectively.

26 pages + 6 pages appendix,3 figures