View PDF

Abstract:Given \(1\le\ell <k \) and \(\delta\geq 0\), let \(\mathbf{PM}(k,\ell,\delta)\) be the decision problem for the existence of perfect matchings in \(n\)-vertex \(k\)-uniform hypergraphs with minimum \(\ell\)-degree at least \(\delta\binom{n-\ell}{k-\ell}\). For \(k\geq 3\), \(\mathbf{PM}(k,\ell,0)\) was one of the first NP-complete problems identified by Karp. Keevash, Knox and Mycroft conjectured that \(\mathbf{PM}(k,\ell,\delta)\) is in P for every \(\delta>1-(1-1/k)^{k-\ell}\) and this was recently verified by the work of Gan--Han, together with a very recent work of Fu et al.
In this paper we study the existence of perfect matchings in the random $p$-sparsification of such $k$-uniform hypergraphs, that is, for $p=p(n)\in [0,1]$, each edge is selected independently with probability \(p\). Building on the structural theory of Gan and Han, we show that the corresponding dense perfect matching results are robust under random sparsification. As consequences, we obtain deterministic polynomial-time algorithms that asymptotically almost surely solve the associated decision problems, as well as lower bounds on the number of perfect matchings in such hypergraphs -- interestingly, such hypergraphs either have no perfect matching, or have $(\Omega(n))^{(1-1/k)n}$ perfect matchings. Moreover, we also establish analogous results for the \(F\)-factor problem in graphs.
Our proofs combine a partial exposure algorithm, the lattice-based absorption method, and a random redistribution method of Kelly, Müyesser and Pokrovskiy, via the framework of spread distributions. A key new ingredient is a lattice-preparation step that separates the contributions of the two classes of robust index vectors arising in the Gan--Han structural theory. Together with the random redistribution method, this allows us to establish the desired spread property in the family of perfect matchings.

Submission history

From: Jingwen Zhao [view email]
[v1] Tue, 15 Jul 2025 14:28:14 UTC (51 KB)
[v2] Sun, 27 Jul 2025 13:25:39 UTC (51 KB)
[v3] Wed, 22 Oct 2025 09:05:09 UTC (51 KB)
[v4] Wed, 29 Jul 2026 10:25:30 UTC (55 KB)