On directed versions of the Hajnal-Szemerédi theorem

DOI10.1017/S0963548315000036zbMATH Open1371.05234arXiv1406.3229OpenAlexW2963269116MaRDI QIDQ5364261FDOQ5364261

Authors: Andrew Treglown 

Publication date: 4 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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'edi 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 $rgeq3$. 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.

Full work available at URL: https://arxiv.org/abs/1406.3229

Recommendations

• A degree sequence Hajnal-Szemerédi theorem
• Tiling directed graphs with tournaments
• An extension of the Hajnal-Szemerédi theorem to directed graphs
• On perfect packings in dense graphs
• A multipartite Hajnal-Szemerédi theorem

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Proof of the Seymour conjecture for large graphs
• The minimum degree threshold for perfect graph packings
• An Ore-type theorem on equitable coloring
• On the Complexity of General Graph Factor Problems
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• An Ore-type theorem for perfect packings in graphs
• On directed versions of the Corrádi-Hajnal corollary
• An extension of the Hajnal-Szemerédi theorem to directed graphs
• Title not available (Why is that?)
• Testing subgraphs in directed graphs
• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• Minimum codegree threshold for \((K^3_4-e)\)-factors
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
• A geometric theory for hypergraph matching
• A new proof of the graph removal lemma
• Triangle packings and 1-factors in oriented graphs
• A note on some embedding problems for oriented graphs
• Variants of the Hajnal-Szemer�di Theorem
• Independent directed triangles in a directed graph
• Disjoint directed quadrilaterals in a directed graph

Cited In (16)

• Clique-factors in graphs with sublinear -independence number
• A degree sequence Hajnal-Szemerédi theorem
• On directed versions of the Corrádi-Hajnal corollary
• A multipartite Hajnal-Szemerédi theorem
• Strengthening Theorems of Dirac and Erdős on Disjoint Cycles
• Triangle factors of graphs without large independent sets and of weighted graphs
• Rainbow spanning structures in graph and hypergraph systems
• Tiling directed graphs with tournaments
• An extension of the Hajnal-Szemerédi theorem to directed graphs
• Minimum number of edges guaranteeing the existence of a \(K_{1, t}\)-factor in a graph
• Embedding clique-factors in graphs with low \(\ell\)-independence number
• Transitive triangle tilings in oriented graphs
• \(H\)-factors in graphs with small independence number
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• A note on some embedding problems for oriented graphs
• Transitive tournament tilings in oriented graphs with large minimum total degree

This page was built for publication: On directed versions of the Hajnal-Szemerédi theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5364261)