Hostname: page-component-745bb68f8f-f46jp Total loading time: 0 Render date: 2025-02-06T13:41:11.234Z Has data issue: false hasContentIssue false
  • English
  • Français

On Directed Versions of the Hajnal–Szemerédi Theorem

Published online by Cambridge University Press:  05 February 2015

ANDREW TREGLOWN
ANDREW TREGLOWN*
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT, UK (e-mail: a.c.treglown@bham.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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].

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Issue 6 , November 2015 , pp. 873 - 928
Copyright
Copyright © Cambridge University Press 2015 

References

[1] Alon, N. and Shapira, A. (2004) Testing subgraphs in directed graphs, J. Comput. System Sci. 69 354–382.Google Scholar
[2] Balogh, J., Lo, A. and Molla, T. Transitive triangle tilings in oriented graphs. Submitted.Google Scholar
[3] Czygrinow, A., DeBiasio, L., Kierstead, H. A. and Molla, T. (2015) An extension of the Hajnal–Szemerédi theorem to directed graphs. Combin. Probab. Comput., accepted, to appear. doi:10.1017/S0963548314000716.Google Scholar
[4] Czygrinow, A., Kierstead, H. A. and Molla, T. (2014) On directed versions of the Corrádi–Hajnal corollary. European J. Combin. 42 1–14.Google Scholar
[5] Fischer, E. (1999) Variants of the Hajnal–Szemerédi theorem. J. Graph Theory 31 275–282.Google Scholar
[6] Fox, J. (2011) A new proof of the graph removal lemma. Ann. of Math. 174 561–579.Google Scholar
[7] Hajnal, A. and Szemerédi, E. (1970) Proof of a conjecture of Erdős. In Combinatorial Theory and its Applications II (Renyi, A., Erdős, P. and Sós, V. T., eds), North-Holland, pp. 601–623.Google Scholar
[8] Hell, P. and Kirkpatrick, D. G. (1983) On the complexity of general graph factor problems, SIAM J. Comput. 12 601–609.Google Scholar
[9] Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley.Google Scholar
[10] Keevash, P. and Mycroft, R. (2014) A geometric theory for hypergraph matching. Mem. Amer. Math. Soc. 233 monograph 1098.Google Scholar
[11] Keevash, P. and Mycroft, R. A multipartite Hajnal–Szemerédi theorem. Submitted.Google Scholar
[12] Keevash, P. and Sudakov, B. (2009) Triangle packings and 1-factors in oriented graphs. J. Combin. Theory Ser. B 99 709–727.Google Scholar
[13] Kierstead, H. A. and Kostochka, A. V. (2008) An Ore-type theorem on equitable coloring. J. Combin. Theory Ser. B 98 226–234.Google Scholar
[14] Komlós, J., Sárközy, G. N. and Szemerédi, E. (1998) Proof of the Seymour conjecture for large graphs. Ann. Combin. 2 43–60.Google Scholar
[15] Kühn, D. and Osthus, D. (2006) Critical chromatic number and the complexity of perfect packings in graphs. In Proc. 17th ACM–SIAM Symposium on Discrete Algorithms: SODA 2006, pp. 851–859.Google Scholar
[16] Kühn, D. and Osthus, D. (2009) The minimum degree threshold for perfect graph packings. Combinatorica 29 65–107.Google Scholar
[17] Kühn, D., Osthus, D. and Treglown, A. (2009) An Ore-type theorem for perfect packings in graphs. SIAM J. Discrete Math. 23 1335–1355.Google Scholar
[18] Lo, A. and Markström, K. (2013) Minimum codegree threshold for (K 4 3-e)-factors. J. Combin. Theory Ser. A 120 708–721.Google Scholar
[19] Lo, A. and Markström, K. F-factors in hypergraphs via absorption, Graphs Combin., to appear.Google Scholar
[20] Rödl, V., Ruciński, A. and Szemerédi, E. (2006) A Dirac-type theorem for 3-uniform hypergraphs. Combin. Probab. Comput. 15 229–251.Google Scholar
[21] Rödl, V., Ruciński, A. and Szemerédi, E. (2009) Perfect matchings in large uniform hypergraphs with large minimum collective degree. J. Combin. Theory Ser. A 116 613–636.Google Scholar
[22] Treglown, A. (2012) A note on some oriented graph embedding problems. J. Graph Theory 69 330–336.Google Scholar
[23] Treglown, A. A degree sequence Hajnal–Szemerédi theorem. Submitted.Google Scholar
[24] Treglown, A. and Zhao, Y. (2012) Exact minimum degree thresholds for perfect matchings in uniform hypergraphs. J. Combin. Theory Ser. A 119 1500–1522.Google Scholar
[25] Wang, H. (2000) Independent directed triangles in a directed graph. Graphs Combin. 16 453–462.Google Scholar
[26] Wang, H. and Zhang, D. (2005) Disjoint directed quadrilaterals in a directed graph. J. Graph Theory 50 91–104.Google Scholar