Tiling transitive tournaments and their blow-ups

الأصل · EN

Let TTₖ denote the transitive tournament on k vertices. Let TT(h,k) denote the graph obtained from TTₖ by replacing each vertex with an independent set of size h ≥ 1. The following result is proved: Let c₂=1/2, c₃=5/6 and cₖ=1-2-k- k for k ≥ 4. For every ε> 0 there exists N=N(ε,h,k) such that for every undirected graph G with n > N vertices and with δ(G) ≥ cₖn, every orientation of G contains vertex disjoint copies of TT(h,k) that cover all but at most εn vertices. In the cases k=2 and k=3 the result is asymptotically tight. For k ≥ 4, cₖ cannot be improved to less than 1-2⁻⁰.⁵ᵏ⁽¹⁺ᵒ⁽¹⁾⁾.