On the Keevash-Knox-Mycroft Conjecture

Abstract

Given $1\le \ell <k$ and $\hat{I}´\ge 0$, let $\text{PM}(k,\ell ,\hat{I}´)$ be the decision problem for the existence of perfect matchings in $n$-vertex $k$-uniform hypergraphs with minimum $\ell$-degree at least $\hat{I}´\left(\genfrac{}{}{0ex}{}{n-\ell }{k-\ell }\right)$. For $k\ge 3$, $\text{PM}(k,\ell ,0)$ was one of the first NP-complete problems by Karp. Keevash, Knox and Mycroft conjectured that $\text{PM}(k,\ell ,\hat{I}´)$ is in P for every $\hat{I}´>1-(1-1/k{)}^{k-\ell }$ and verified the case $\ell =k-1$. In this paper we show that this problem can be reduced to the study of the minimum $\ell$-degree condition forcing the existence of fractional perfect matchings. Together with existing results on fractional perfect matchings, this solves the conjecture of Keevash, Knox and Mycroft for $\ell \ge 0.4k$. Moreover, we also supply an algorithm that outputs a perfect matching, provided that one exists.

v1 is the conference version; v2, v3 are the journal versions; v4 is the final (full) version; v5 post-publication version: added Proposition 4.1 to correct a falsely claimed upper bound on the order of the coset group