Perfect Matchings in Random Sparsifications of Dense Hypergraphs

The decision problem of perfect matchings in uniform hypergraphs is famously an NP-complete problem. It has been shown by Keevash–Knox–Mycroft [STOC, 2013] that for every \(\varepsilon \gt 0\), such decision problem restricted to \(k\)-uniform hypergraphs \(H\) satisfying that every \((k-1)\)-set of vertices is in at least \((1/k+\varepsilon)|H|\) edges is tractable, and the quantity \(1/k\) is best possible. 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]\), every edge is kept with probability \(p\) independent of others. As a consequence, we give a polynomial-time algorithm that with high probability solves the decision problem; we also derive effective bounds on the number of perfect matchings in such hypergraphs. At last, similar results are obtained for the \(F\)-factor problem in graphs.