2015/03/02 by Clemens, Dennis, Ehrenmüller, Julia
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1503.00438
A conjecture by Aharoni and Berger states that every family of n matchings of size n+1 in a bipartite multigraph contains a rainbow matching of size n. In this paper we prove that matching sizes of (3/2 + o(1)) n suffice to guarantee such a rainbow matching, which is asymptotically the same bound as the best known one in case we only aim to find a rainbow matching of size n-1. This improves previous results by Aharoni, Charbit and Howard, and Kotlar and Ziv.