Perfect Matchings in Random Sparsifications of Dense Hypergraphs

Given 1 ≤ ℓ < k and δ ≥ 0, let PM(k, ℓ, δ) be the decision problem for the existence of perfect matchings in n-vertex k-uniform hypergraphs with minimum ℓ-degree at least δ n-ℓ k-ℓ . For k ≥ 3, PM(k, ℓ, 0) was one of the first NP-complete problems identified by Karp. Keevash, Knox and Mycroft conjectured that PM(k, ℓ, δ) is in P for every δ > 1 -(1 -1/k) k-ℓ 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) ∈ [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 (Ω(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.