On directed versions of the Hajnal-Szemerédi theorem

Research output: Contribution to journalArticle

Colleges, School and Institutes

Abstract

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 characterises the minimum degree that ensures a graph G contains a perfect K_r-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 (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 concerning almost perfect matchings in hypergraphs as well as the Directed Graph Removal lemma.

Details

Original languageEnglish
Pages (from-to)873-928
Number of pages56
JournalCombinatorics, Probability and Computing
Volume24
Issue number6
Early online date5 Feb 2015
Publication statusPublished - Nov 2015