论文标题
随机超图中的狄拉克型定理
Dirac-type theorems in random hypergraphs
论文作者
论文摘要
对于正整数$ d <k $，$ n $由$ k $排除，让$ m_ {d}（k，n）$为最小$ d $ -Degree，以确保在$ k $均匀的 - 均匀的超图中存在完美匹配。在图案中（其中$ k = 2 $），dirac的经典定理说$ m_ {1}（2，n）= \ lceil n/2 \ rceil $。但是，总的来说，我们对$ m_ {d}（k，n）$的值的理解仍然非常有限，这是确定或近似这些值的积极研究主题。在本文中，我们证明了与随机超图相对于随机超图的“转移”定理。具体而言，对于任何$ d <k $，任何$ \ varepsilon> 0 $和任何“不小” $ p $，我们证明一个随机的$ k $ k $均匀的hypergraph $ g $带有$ n $ pertices and gend pertices and Edge Pripities and Edge p $通常具有每个Spanning $ G $的属性，每个跨度为$ g $，至少是$ gertem $ $ $ p $ p $ p $ __+vareps i \ vareps a;匹配。我们证明的一个有趣的方面是吸收方法的“非构造性”应用，它使我们能够证明在$ m_ {d}（k，n）$的情况下，而无需实际知道其值。
For positive integers $d<k$ and $n$ divisible by $k$, let $m_{d}(k,n)$ be the minimum $d$-degree ensuring the existence of a perfect matching in a $k$-uniform hypergraph. In the graph case (where $k=2$), a classical theorem of Dirac says that $m_{1}(2,n)=\lceil n/2\rceil$. However, in general, our understanding of the values of $m_{d}(k,n)$ is still very limited, and it is an active topic of research to determine or approximate these values. In this paper we prove a "transference" theorem for Dirac-type results relative to random hypergraphs. Specifically, for any $d< k$, any $\varepsilon>0$ and any "not too small" $p$, we prove that a random $k$-uniform hypergraph $G$ with $n$ vertices and edge probability $p$ typically has the property that every spanning subgraph of $G$ with minimum degree at least $(1+\varepsilon)m_{d}(k,n)p$ has a perfect matching. One interesting aspect of our proof is a "non-constructive" application of the absorbing method, which allows us to prove a bound in terms of $m_{d}(k,n)$ without actually knowing its value.
