2015/04/21 by Pokrovskiy, Alexey
#05B15 #05C20 #05C40 #05C70 (Primary) #05D15 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1504.05373
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 ϕn + o(n) where ϕ≈ 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.