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.
@article{10_37236_3742,
author = {Roman Glebov and Benny Sudakov and Tibor Szab\'o},
title = {How many colors guarantee a rainbow matching?},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {1},
doi = {10.37236/3742},
zbl = {1300.05097},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3742/}
}
TY - JOUR
AU - Roman Glebov
AU - Benny Sudakov
AU - Tibor Szabó
TI - How many colors guarantee a rainbow matching?
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/3742/
DO - 10.37236/3742
ID - 10_37236_3742
ER -
%0 Journal Article
%A Roman Glebov
%A Benny Sudakov
%A Tibor Szabó
%T How many colors guarantee a rainbow matching?
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/3742/
%R 10.37236/3742
%F 10_37236_3742
Roman Glebov; Benny Sudakov; Tibor Szabó. How many colors guarantee a rainbow matching?. The electronic journal of combinatorics, Tome 21 (2014) no. 1. doi: 10.37236/3742
