Perfect matchings in random sparsifications of Dirac hypergraphs

arXiv2211.01325MaRDI QIDQ6506950FDOQ6506950

Authors: Dong Yeap Kang, Tom Kelly, Daniela Kühn, Deryk Osthus, Vincent Pfenninger 

Abstract: For all integers $ngeqk>dgeq1$, let $m_d(k,n)$ be the minimum integer $Dgeq0$ such that every $k$-uniform $n$-vertex hypergraph $mathcalH$ with minimum $d$-degree $delt{a}_d(mathcalH)$ at least $D$ has an optimal matching. For every fixed integer $kgeq3$, we show that for $ninkmathbbN$ and $p=Omega(n^{-k+1}logn)$, if $mathcalH$ is an $n$-vertex $k$-uniform hypergraph with $delt{a}_{k-1}(mathcalH)geq{m}_{k-1}(k,n)$, then a.a.s. its $p$-random subhypergraph $mathcal{H}_p$ contains a perfect matching ($m_{k-1}(k,n)$ was determined by R"{o}dl, Ruci'nski, and Szemer'edi for all large $ninkmathbbN$). Moreover, for every fixed integer $d<k$ and $gamma>0$, we show that the same conclusion holds if $mathcalH$ is an $n$-vertex $k$-uniform hypergraph with $$. 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, $mathcalH$ has at least $exp((1-1/k)nlogn-Theta(n))$ many perfect matchings, which is best possible up to a $exp(Theta(n))$ factor.

This page was built for publication: Perfect matchings in random sparsifications of Dirac hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6506950)