Matchings in multipartite hypergraphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929536722010112 |
|---|---|
| author | Bowtell, Candida Mycroft, Richard |
| author_facet | Bowtell, Candida Mycroft, Richard |
| contents | A folklore result on matchings in graphs states that if $G$ is a bipartite graph whose vertex classes $A$ and $B$ each have size $n$, with $\mathrm{deg}(u) \geq a$ for every $u \in A$ and $\mathrm{deg}(v) \geq b$ for every $v \in B$, then $G$ admits a matching of size $\min\{n, a+b\}$. In this paper we establish the analogous result for large $k$-partite $k$-uniform hypergraphs, answering a question of Han, Zang and Zhao, who previously demonstrated that this result holds under the additional condition that the minimum degrees into at least two of the vertex classes are large. A key part of our proof is a study of rainbow matchings under a combination of degree and multiplicity conditions, which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_05219 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Matchings in multipartite hypergraphs Bowtell, Candida Mycroft, Richard Combinatorics 05C65, 05C70 A folklore result on matchings in graphs states that if $G$ is a bipartite graph whose vertex classes $A$ and $B$ each have size $n$, with $\mathrm{deg}(u) \geq a$ for every $u \in A$ and $\mathrm{deg}(v) \geq b$ for every $v \in B$, then $G$ admits a matching of size $\min\{n, a+b\}$. In this paper we establish the analogous result for large $k$-partite $k$-uniform hypergraphs, answering a question of Han, Zang and Zhao, who previously demonstrated that this result holds under the additional condition that the minimum degrees into at least two of the vertex classes are large. A key part of our proof is a study of rainbow matchings under a combination of degree and multiplicity conditions, which may be of independent interest. |
| title | Matchings in multipartite hypergraphs |
| topic | Combinatorics 05C65, 05C70 |
| url | https://arxiv.org/abs/2403.05219 |