Bounded degree graphs and hypergraphs with no full rainbow matchings
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908718816296960 |
|---|---|
| author | Wdowinski, Ronen |
| author_facet | Wdowinski, Ronen |
| contents | Given a multi-hypergraph $G$ that is edge-colored into color classes $E_1, \ldots, E_n$, a full rainbow matching is a matching of $G$ that contains exactly one edge from each color class $E_i$. One way to guarantee the existence of a full rainbow matching is to have the size of each color class $E_i$ be sufficiently large compared to the maximum degree of $G$. In this paper, we apply a simple iterative method to construct edge-colored multi-hypergraphs with a given maximum degree, large color classes, and no full rainbow matchings. First, for every $r \ge 1$ and $Δ\ge 2$, we construct edge-colored $r$-uniform multi-hypergraphs with maximum degree $Δ$ such that each color class has size $|E_i| \ge rΔ- 1$ and there is no full rainbow matching, which demonstrates that a theorem of Aharoni, Berger, and Meshulam (2005) is best possible. Second, we construct properly edge-colored multigraphs with no full rainbow matchings which disprove conjectures of Delcourt and Postle (2022). Finally, we apply results on full rainbow matchings to list edge-colorings and prove that a color degree generalization of Galvin's theorem (1995) does not hold. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_06029 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Bounded degree graphs and hypergraphs with no full rainbow matchings Wdowinski, Ronen Combinatorics Given a multi-hypergraph $G$ that is edge-colored into color classes $E_1, \ldots, E_n$, a full rainbow matching is a matching of $G$ that contains exactly one edge from each color class $E_i$. One way to guarantee the existence of a full rainbow matching is to have the size of each color class $E_i$ be sufficiently large compared to the maximum degree of $G$. In this paper, we apply a simple iterative method to construct edge-colored multi-hypergraphs with a given maximum degree, large color classes, and no full rainbow matchings. First, for every $r \ge 1$ and $Δ\ge 2$, we construct edge-colored $r$-uniform multi-hypergraphs with maximum degree $Δ$ such that each color class has size $|E_i| \ge rΔ- 1$ and there is no full rainbow matching, which demonstrates that a theorem of Aharoni, Berger, and Meshulam (2005) is best possible. Second, we construct properly edge-colored multigraphs with no full rainbow matchings which disprove conjectures of Delcourt and Postle (2022). Finally, we apply results on full rainbow matchings to list edge-colorings and prove that a color degree generalization of Galvin's theorem (1995) does not hold. |
| title | Bounded degree graphs and hypergraphs with no full rainbow matchings |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.06029 |