Rainbow matchings and rainbow connectedness

Abstract

Aharoni and Berger conjectured that every bipartite graph which is the union of n matchings of size n + 1 contains a rainbow matching of size n. This conjecture is a generalization of several old conjectures of Ryser, Brualdi, and Stein about transversals in Latin squares. There have been many recent partial results about the Aharoni-Berger Conjecture. In the case when the matchings are much larger than n + 1, the best bound is currently due to Clemens and Ehrenmüller who proved the conjecture when the matchings are of size at least 3n/2 + o(n). When the matchings are all edge-disjoint and perfect, then the best result follows from a theorem of Häggkvist and Johansson which implies the conjecture when the matchings have size at least n + o(n). In this paper we show that the conjecture is true when the matchings have size n + o(n) and are all edge-disjoint (but not necessarily perfect). We also give an alternative argument to prove the conjecture when the matchings have size at least $\varphi n+o(n)$ where $\varphi \approx 1.618$ is the Golden Ratio. Our proofs involve studying connectedness in coloured, directed graphs. The notion of connectedness that we introduce is new, and perhaps of independent interest.

arXiv comment17 pages, 1 figure