DECISION PROBLEM FOR PERFECT MATCHINGS IN DENSE k-UNIFORM HYPERGRAPHS.

For any γ > 0, Keevash, Knox and Mycroft (2015) constructed a polynomial-time algorithm which determines the existence of perfect matchings in any n-vertex k-uniform hypergraph whose minimum codegree is at least n/k + γn. We prove a structural 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. [ABSTRACT FROM AUTHOR]