Perfect matchings in random sparsifications of Dirac hypergraphs

Abstract

For all integers $n\ge k>d\ge 1$, let $m_d(k,n)$ be the minimum integer $D\ge 0$ such that every $k$-uniform $n$-vertex hypergraph $\mathcal{H}$ with minimum $d$-degree $\hat{I}{´}_d(\mathcal{H})$ at least $D$ has an optimal matching. For every fixed integer $k\ge 3$, we show that for $n\in k\mathbb{N}$ and $p=\hat{I}\text{c◯}(n^{-k+1}\log n)$, if $\mathcal{H}$ is an $n$-vertex $k$-uniform hypergraph with $\hat{I}{´}_{k-1}(\mathcal{H})\ge m_{k-1}(k,n)$, then a.a.s.\ its $p$-random subhypergraph ${\mathcal{H}}_p$ contains a perfect matching. Moreover, for every fixed integer $d<k$ and ${\hat{I}}^3>0$, we show that the same conclusion holds if $\mathcal{H}$ is an $n$-vertex $k$-uniform hypergraph with $\hat{I}{´}_d(\mathcal{H})\ge m_d(k,n)+{\hat{I}}^3\left(\genfrac{}{}{0ex}{}{n-d}{k-d}\right)$. Both of these results strengthen Johansson, Kahn, and Vu's seminal solution to Shamir's problem and can be viewed as ``robust'' versions of hypergraph Dirac-type results. In addition, we also show that in both cases above, $\mathcal{H}$ has at least $\exp ((1-1/k)n\log n-\hat{I}˜(n))$ many perfect matchings, which is best possible up to an $\exp (\hat{I}˜(n))$ factor.

Final version, to appear in Combinatorica (26 pages + 2 page appendix); Theorem 1.5 was proved in independent work of Pham, Sah, Sawhney, and Simkin (arxiv:2210.03064)