论文标题
在随机稀疏中的完美匹配Dirac Hypergraphs
Perfect matchings in random sparsifications of Dirac hypergraphs
论文作者
论文摘要
For all integers $n \geq k > d \geq 1$, let $m_{d}(k,n)$ be the minimum integer $D \geq 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.对于每个固定的整数$ k \ geq 3 $，我们证明$ n \ in k \ mathbb {n} $和$ p =ω（n^{ - k+1} \ log n）$，如果$ \ mathcal h $是$ n $ n $ -vertex $ k $ k $ - 均匀的超级ge，则与$ nifter-niftergraph搭配$ ge gee geequ fe m_ {k-1}（k，n）$，然后A.A.S. \ $ p $ -random subhypergraph $ \ mathcal h_p $包含完美的匹配。此外，对于每个固定的整数$ d <k $和$γ> 0 $，我们表明，如果$ \ \ \ \ \ \ \ m natival h $是$ n $ -vertex $ k $ k $ -k $ ruilypraph，则使用$δ_d（\ nathcal h）\ geq m_ {d}（k，n） +γ\ binom binom，这两种结果都增强了Johansson，Kahn和VU对Shamir问题的开创性解决方案，可以看作是HyperGraph Dirac-type结果的``稳定''版本。此外，我们还表明，在上述两种情况下，$ \ MATHCAL H $至少具有$ \ exp（（1-1/k）n \ log n -θ（n））$许多完美的匹配，最好是$ \ exp（θ（n））$。
For all integers $n \geq k > d \geq 1$, let $m_{d}(k,n)$ be the minimum integer $D \geq 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 \geq 3$, we show that for $n \in k \mathbb{N}$ and $p = Ω(n^{-k+1} \log n)$, if $\mathcal H$ is an $n$-vertex $k$-uniform hypergraph with $δ_{k-1}(\mathcal H) \geq 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 $γ> 0$, we show that the same conclusion holds if $\mathcal H$ is an $n$-vertex $k$-uniform hypergraph with $δ_d(\mathcal H) \geq m_{d}(k,n) + γ\binom{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$ has at least $\exp((1-1/k)n \log n - Θ(n))$ many perfect matchings, which is best possible up to an $\exp(Θ(n))$ factor.
