How Many Colors Guarantee a Rainbow Matching?

Abstract

Given a coloring of the edges of a multi-hypergraph, a rainbow $t$-matching is a collection of $t$ disjoint edges, each having a different color. In this note we study the problem of finding a rainbow $t$-matching in an $r$-partite $r$-uniform multi-hypergraph whose edges are colored with $f$ colors such that every color class is a matching of size $t$. This problem was posed by Aharoni and Berger, who asked to determine the minimum number of colors which guarantees a rainbow matching. We improve on the known upper bounds for this problem for all values of the parameters. In particular for every fixed $r$, we give an upper bound which is polynomial in $t$, improving the superexponential estimate of Alon. Our proof also works in the setting not requiring the hypergraph to be $r$-partite.