An improved bound on the sizes of matchings guaranteeing a rainbow matching (Q281599): Difference between revisions

Summary: A conjecture by \textit{R. Aharoni} and \textit{E. Berger} [Electron. J. Comb. 16, No. 1, Research Paper R119, 9 p. (2009; Zbl 1186.05118)] 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 \((\frac {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 \textit{R. Aharoni} et al. [J. Graph Theory 78, No. 2, 143--156 (2015; Zbl 1306.05187)], and \textit{D. Kotlar} and \textit{R. Ziv} [Eur. J. Comb. 38, 97--101 (2014; Zbl 1282.05210)].