Rainbow matchings and rainbow connectedness (Q510322): Difference between revisions

Summary: \textit{R. Aharoni} and \textit{E. Berger} [Electron. J. Comb. 16, No. 1, Research Paper R119, 9 p. (2009; Zbl 1186.05118)] conjectured that every collection of \(n\) matchings of size \(n+1\) in a bipartite graph contains a rainbow matching of size \(n\). This conjecture is related to several old conjectures of \textit{R. A. Brualdi} and \textit{H. J. Ryser} [Combinatorial matrix theory. Cambridge etc.: Cambridge University Press. (1991; Zbl 0746.05002)], and \textit{S. K. Stein} [Pac. J. Math. 59, No. 2, 567--575 (1975; Zbl 0302.05015)] about transversals in Latin squares. There have been many recent partial results about the Aharoni-Berger Conjecture. The conjecture is known to hold when the matchings are much larger than \(n+1\). The best bound is currently due to \textit{R. Aharoni} et al. [``Representation of large matchings in bipartite graphs'', Preprint, \url{arXiv:1601.00943}] who proved the conjecture when the matchings are of size at least \(3n/2+1\). When the matchings are all edge-disjoint and perfect, the best result follows from a theorem of \textit{R. Häggkvist} and \textit{A. Johansson} [Comb. Probab. Comput. 17, No. 4, 519--536 (2008; Zbl 1152.05019)] 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 \(\phi n+o(n)\) where \(\phi\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.