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

Summary: Given a collection of matchings \({\mathcal M}= (M_1,M_2,\dots,M_q)A\) (repetitions allowed), a matching \(M\) contained in \(\cup{\mathcal M}\) is said to be \(s\)-rainbow for \({\mathcal M}A\) 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 \(\varphi:M\to[q]\) such that \(e\in M_{\varphi(e)}\) for all \(e\in M\), and \(|\operatorname{Im}{\varphi}|\geq 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)\geq 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.