On Directed Versions of the Hajnal–Szemerédi Theorem
On Directed Versions of the Hajnal–Szemerédi Theorem
复制标题
DOI：
10.1017/s0963548315000036
复制
发表时间：
2014-06
期刊：
影响因子：
--
通讯作者：
Andrew Treglown
中科院分区：
文献类型：
--
作者：
Andrew Treglown
如果存在一组覆盖 G 中所有顶点的 H 的顶点不相交副本，我们就说 (di) 图 G 具有完美的 H 包装。开创性的 Hajnal-Szemerédi 定理描述了确保图 G 包含完美 Kr 包装的最小度。在本文中，我们证明了以下有向图的类比：假设 T 是 r 个顶点上的锦标赛，G 是足够大的 n 阶有向图，其中 r 除以 n。如果 G 的最小入度和出度至少为 (1−1/r)n，则 G 包含完美的 T 包装。在 T 是循环三角形的情况下，这个结果验证了 Czygrinow、Kierstead 和 Molla 最近的猜想 [4]（对于大有向图）。此外，在 T 是传递的情况下，我们推测 G 中的每个顶点具有足够大的入度或出度就足够了。我们对传递三角形证明了这个猜想，并且对所有 r ⩾ 3 进行了渐进证明。我们的方法利用了 Keevash 和 Mycroft [10] 关于超图中几乎完美匹配的结果以及有向图去除引理 [1, 6]。
We say that a (di)graph G has a perfect H-packing if there exists a set of vertex-disjoint copies of H which cover all the vertices in G. The seminal Hajnal–Szemerédi theorem characterizes the minimum degree that ensures a graph G contains a perfect Kr -packing. In this paper we prove the following analogue for directed graphs: Suppose that T is a tournament on r vertices and G is a digraph of sufficiently large order n where r divides n. If G has minimum in- and outdegree at least (1−1/r)n then G contains a perfect T-packing. In the case when T is a cyclic triangle, this result verifies a recent conjecture of Czygrinow, Kierstead and Molla [4] (for large digraphs). Furthermore, in the case when T is transitive we conjecture that it suffices for every vertex in G to have sufficiently large indegree or outdegree. We prove this conjecture for transitive triangles and asymptotically for all r ⩾ 3. Our approach makes use of a result of Keevash and Mycroft [10] concerning almost perfect matchings in hypergraphs as well as the Directed Graph Removal Lemma [1, 6].