Rainbow matchings in \(r\)-partite \(r\)-graphs

Ron Aharoni ; Eli Berger

The electronic journal of combinatorics, Tome 16 (2009) no. 1

Résumé

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.

Détail

DOI : 10.37236/208

Classification : 05D15