Sharp bounds for rainbow matchings in hypergraphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909344866500608 |
|---|---|
| author | Pohoata, Cosmin Sauermann, Lisa Zakharov, Dmitrii |
| author_facet | Pohoata, Cosmin Sauermann, Lisa Zakharov, Dmitrii |
| contents | 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ó. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_07580 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Sharp bounds for rainbow matchings in hypergraphs Pohoata, Cosmin Sauermann, Lisa Zakharov, Dmitrii Combinatorics 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ó. |
| title | Sharp bounds for rainbow matchings in hypergraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2212.07580 |