论文标题
超图中彩虹匹配的急剧界限
Sharp bounds for rainbow matchings in hypergraphs
论文作者
论文摘要
假设我们得到了$ m_1的匹配，....，$ r $ rust-subrich hypergraph中的$ t $的m_n $，让我们想到每个匹配都具有不同的颜色。 $ n $需要多大（就$ t $和$ r $而言），以便我们总是可以找到大小$ t $的彩虹匹配？这个问题首先是Aharoni和Berger引入的，此后由几位不同的作者研究。例如，Alon发现了与Addive Compinatorics的Erdős-ginzburg- Ziv问题的有趣联系，这意味着$ n $的某些下限。 对于任何固定的均匀性$ r \ ge 3 $，我们将此问题回答为常数因素，具体取决于$ r $，表明答案是按$ t^{r} $的顺序。此外，对于任何固定的$ t $和大$ r $，我们确定答案要降至较低订单因素。在假定基础超图为$ r $ - 部分的环境中，我们还证明了类似的结果。我们的结果解决了Alon和Glebov-Sudakov-Szabó的问题。
Suppose we are given matchings $M_1,....,M_N$ of size $t$ in some $r$-uniform hypergraph, and let us think of each matching having a different color. How large does $N$ need to be (in terms of $t$ and $r$) such that we can always find a rainbow matching of size $t$? This problem was first introduced by Aharoni and Berger, and has since been studied by several different authors. For example, Alon discovered an intriguing connection with the Erdős--Ginzburg--Ziv problem from additive combinatorics, which implies certain lower bounds for $N$. For any fixed uniformity $r \ge 3$, we answer this problem up to constant factors depending on $r$, showing that the answer is on the order of $t^{r}$. Furthermore, for any fixed $t$ and large $r$, we determine the answer up to lower order factors. We also prove analogous results in the setting where the underlying hypergraph is assumed to be $r$-partite. Our results settle questions of Alon and of Glebov-Sudakov-Szabó.
