Cooperative conditions for the existence of rainbow matchings


Abstract in English

Let $k>1$, and let $mathcal{F}$ be a family of $2n+k-3$ non-empty sets of edges in a bipartite graph. If the union of every $k$ members of $mathcal{F}$ contains a matching of size $n$, then there exists an $mathcal{F}$-rainbow matching of size $n$. Upon replacing $2n+k-3$ by $2n+k-2$, the result can be proved both topologically and by a relatively simple combinatorial argument. The main effort is in gaining the last $1$, which makes the result sharp.

Download