论文标题
在Keevash-Knox-Mycroft猜想上
On the Keevash-Knox-Mycroft Conjecture
论文作者
论文摘要
Given $1\le \ell <k$ and $δ\ge0$, let $\textbf{PM}(k,\ell,δ)$ be the decision problem for the existence of perfect matchings in $n$-vertex $k$-uniform hypergraphs with minimum $\ell$-degree at least $δ\binom{n-\ell}{k-\ell}$.对于$ k \ ge 3 $，$ \ textbf {pm}（k，\ ell，0）$是KARP的第一个NP完整问题之一。 Keevash，Knox和Mycroft猜想$ \ textbf {pm}（k，\ ell，δ）$在p中，每$δ> 1-（1-1/k）^{k- \ ell} $，并验证了case $ \ \ ell = ell = ell = el = k-1 $。 在本文中，我们表明，可以将这个问题简化为对最低$ \ ell $ $ - 度量条件的研究，从而迫使存在分数完美匹配。连同分数完美匹配的现有结果，这解决了Keevash，Knox和Mycroft的猜想，以$ \ ell \ ge 0.4k $。此外，我们还提供了一种输出完美匹配的算法，只要存在一个算法即可。
Given $1\le \ell <k$ and $δ\ge0$, let $\textbf{PM}(k,\ell,δ)$ be the decision problem for the existence of perfect matchings in $n$-vertex $k$-uniform hypergraphs with minimum $\ell$-degree at least $δ\binom{n-\ell}{k-\ell}$. For $k\ge 3$, $\textbf{PM}(k,\ell,0)$ was one of the first NP-complete problems by Karp. Keevash, Knox and Mycroft conjectured that $\textbf{PM}(k, \ell, δ)$ is in P for every $δ> 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.
