Rainbow Matchings in $r$-Partite $r$-Graphs
Ron Aharoni, Eli Berger · The Electronic Journal of Combinatorics · 2009
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2009
Abstract
Given a collection of matchings ${\cal M} = (M_1, M_2, \ldots, M_q)$ (repetitions allowed), a matching $M$ contained in $\bigcup {\cal M}$ is said to be $s$-rainbow for ${\cal M}$ if it contains representatives from $s$ matchings $M_i$ (where each edge is allowed to represent just one $M_i$). Formally, this means that there is a function $\phi: M \to [q]$ such that $e \in M_{\phi(e)}$ for all $e \in M$, and $|Im(\phi)|\ge s$. Let $f(r,s,t)$ be the maximal $k$ for which there exists a set of $k$ matchings of size $t$ in some $r$-partite hypergraph, such that there is no $s$-rainbow matching of size $t$.
We prove that $f(r,s,t)\ge 2^{r-1}(s-1)$, make the conjecture that equality holds for all values of $r,s$ and $t$ and prove the conjecture when $r=2$ or $s=t=2$. In the case $r=3$, a stronger conjecture is that in a $3$-partite $3$-graph if all vertex degrees in one side (say $V_1$) are strictly larger than all vertex degrees in the other two sides, then there exists a matching of $V_1$. This conjecture is at the same time also a strengthening of a famous conjecture, described below, of Ryser, Brualdi and Stein. We prove a weaker version, in which the degrees in $V_1$ are at least twice as large as the degrees in the other sides.
We also formulate a related conjecture on edge colorings of $3$-partite $3$-graphs and prove a similarly weakened version.
Open the resolved locator · 10.37236/208
Metadata licence: OpenAlex metadata (CC0)