错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Perfect Matchings in Random Sparsifications of Dirac Hypergraphs

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

摘要

For all integers \(n \ge k > d \ge 1\) n k > d 1 , let \(m_{d}(k,n)\) m d ( k , n ) be the minimum integer \(D \ge 0\) D 0 such that every k-uniform n-vertex hypergraph \({\mathcal {H}}\) H with minimum d-degree \(\delta _{d}({\mathcal {H}})\) δ d ( H ) at least D has an optimal matching. For every fixed integer \(k \ge 3\) k 3 , we show that for \(n \in k \mathbb {N}\) n k N and \(p = \Omega (n^{-k+1} \log n)\) p = Ω ( n - k + 1 log n ) , if \({\mathcal {H}}\) H is an n-vertex k-uniform hypergraph with \(\delta _{k-1}({\mathcal {H}}) \ge m_{k-1}(k,n)\) δ k - 1 ( H ) m k - 1 ( k , n ) , then a.a.s. its p-random subhypergraph \({\mathcal {H}}_p\) H p contains a perfect matching. Moreover, for every fixed integer \(d < k\) d < k and \(\gamma > 0\) γ > 0 , we show that the same conclusion holds if \({\mathcal {H}}\) H is an n-vertex k-uniform hypergraph with \(\delta _d({\mathcal {H}}) \ge m_{d}(k,n) + \gamma \left( {\begin{array}{c}n - d\\ k - d\end{array}}\right) \) δ d ( H ) m d ( k , n ) + γ n - d k - 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}}\) H has at least \(\exp ((1-1/k)n \log n - \Theta (n))\) exp ( ( 1 - 1 / k ) n log n - Θ ( n ) ) many perfect matchings, which is best possible up to an \(\exp (\Theta (n))\) exp ( Θ ( n ) ) factor.