Decision problem for Perfect Matchings in Dense k-uniform Hypergraphs

Abstract

For any $\gamma >0$, Keevash, Knox and Mycroft constructed a polynomial-time algorithm to determine the existence of perfect matchings in any $n$-vertex $k$-uniform hypergraph whose minimum codegree is at least $n/k+\gamma n$. We prove a structure theorem that enables us to determine the existence of a perfect matching for any $k$-uniform hypergraph with minimum codegree at least $n/k$. This solves a problem of Karpiński, Ruciński and Szymańska completely. Our proof uses a lattice-based absorbing method.

Accepted by Transactions of the AMS. arXiv admin note: substantial text overlap with arXiv:1307.2608 by other authors

References in corpus (2)

• Polynomial-time perfect matchings in dense hypergraphs
• Near Perfect Matchings in $k$-uniform Hypergraphs

Cited by in corpus (4)

• Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
• Polynomial-time perfect matchings in dense hypergraphs
• The complexity of perfect matchings and packings in dense hypergraphs
• Minimum codegree threshold for $C_6^3$-factors in $3$-uniform Hypergraphs