Polynomial-time perfect matchings in dense hypergraphs
Polynomial-time perfect matchings in dense hypergraphs
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 …