Tiling transitive tournaments and their blow-ups (Q1425167): Difference between revisions

Let \(TT_k\) be the transitive tournament on \(k\) vertices and let \(TT(h,k)\) be the digraph obtained from \(TT_k\) by replacing each vertex of \(TT_k\) with an independent set of size \(h\geq 1\). Define \(c_2=1/2\), \(c_3=5/6\) and \(c_k=1-2^{-k-\log k}\), for \(k\geq 4\). Using the directed version of Szemerédi's regularity lemma, the author proves that for every \(\varepsilon >0\) there exists \(N=N(\varepsilon,h,k)\) such that for every undirected graph \(G\) on \(n>N\) vertices and with \(\delta (G)\geq c_kn\), every orientation of \(G\) contains vertex-disjoint copies of \(TT(h,k)\) that cover at least \(n(1-\varepsilon)\) vertices. For \(k=2,3\) the result is asymptotically tight and for \(k\geq 4\), the lower bound for \(c_k\) proved by the author is \(1-2^{-0.5k(1+o(1))}\).