Polynomial-time perfect matchings in dense hypergraphs

Abstract

Let $H$ be a $k$-graph on $n$ vertices, with minimum codegree at least $n/k+cn$ for some fixed $c>0$. In this paper we construct a polynomial-time algorithm which finds either a perfect matching in $H$ or a certificate that none exists. This essentially solves a problem of Karpiński, Ruciński and Szymańska; Szymańska previously showed that this problem is NP-hard for a minimum codegree of $n/k-cn$. Our algorithm relies on a theoretical result of independent interest, in which we characterise any such hypergraph with no perfect matching using a family of lattice-based constructions.

64 pages. Update includes minor revisions. To appear in Advances in Mathematics

References in corpus (2)

• Near Perfect Matchings in $k$-uniform Hypergraphs
• Decision problem for Perfect Matchings in Dense k-uniform Hypergraphs

Cited by in corpus (9)

• The existence of designs
• Near Perfect Matchings in $k$-uniform Hypergraphs II
• Decision problem for Perfect Matchings in Dense k-uniform Hypergraphs
• The complexity of perfect matchings and packings in dense hypergraphs
• On Perfect Matchings in $k$-complexes
• Packing k-partite k-uniform hypergraphs
• On Perfect Matchings and tilings in uniform Hypergraphs
• Embedding clique-factors in graphs with low $\ell$-independence number
• Finding matchings in dense hypergraphs