How many colors guarantee a rainbow matching? (Q405108): Difference between revisions

Summary: 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 \textit{R. Aharoni} and \textit{E. Berger} [ibid. 16, No. 1, Research Paper R119, 9 p. (2009; Zbl 1186.05118)], 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 \textit{N. Alon} [Mosc. J. Comb. Number Theory 1, No. 1, 3--10 (2011; Zbl 1255.05144)]. Our proof also works in the setting not requiring the hypergraph to be \(r\)-partite.