Abstract
For all integers n≥k>d≥1, let md(k,n) be the minimum integer D≥0 such that every k-uniform n-vertex hypergraph H with minimum d-degree δd(H) at least D has an optimal matching. For every fixed integer k≥3, we show that for n∈kN and p=Ω(n−k+1log n), if H is an n-vertex k-uniform hypergraph with δk−1(H)≥mk−1(k,n), then a.a.s.\ its p-random subhypergraph Hp contains a perfect matching. Moreover, for every fixed integer d < k and
γ > 0, we show that the same conclusion holds if H is an n-vertex k-uniform hypergraph with δd(H)≥md(k,n)+γ(n−dk−d). 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, H has at least exp((1−1/k)nlogn−Θ(n)) many perfect matchings, which is best possible up to an exp(Θ(n)) factor.
γ > 0, we show that the same conclusion holds if H is an n-vertex k-uniform hypergraph with δd(H)≥md(k,n)+γ(n−dk−d). 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, H has at least exp((1−1/k)nlogn−Θ(n)) many perfect matchings, which is best possible up to an exp(Θ(n)) factor.
Original language | English |
---|---|
Number of pages | 34 |
Journal | Combinatorica |
Early online date | 5 Aug 2024 |
DOIs | |
Publication status | E-pub ahead of print - 5 Aug 2024 |