2022/11/02 by Dong Yeap Kang, Tom Kelly, Kang, Dong Yeap +7 · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2211.01325
openalex publication_date 2022/11/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \mathcal H with minimum d-degree δd(\mathcal H) at least D has an optimal matching. For every fixed integer k ≥ 3, we show that for n ∈ k ℕ and p = Ω(n-k+1 log n), if \mathcal H is an n-vertex k-uniform hypergraph with δk-1(\mathcal H) ≥ mk-1(k,n), then a.a.s. its p-random subhypergraph \mathcal Hp contains a perfect matching. Moreover, for every fixed integer d < k and γ> 0, we show that the same conclusion holds if \mathcal H is an n-vertex k-uniform hypergraph with δd(\mathcal H) ≥ md(k,n) + γ\binomn - 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, \mathcal H has at least exp((1-1/k)n log n - Θ(n)) many perfect matchings, which is best possible up to an exp(Θ(n)) factor.