Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-25T17:30:26.707Z 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: [email protected])
Get access Rights & Permissions [Opens in a new window]

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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