Rainbow matchings and rainbow connectedness

Alexey Pokrovskiy¹

¹ETH, Zurich

The electronic journal of combinatorics, Tome 24 (2017) no. 1

Résumé

Aharoni and Berger 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 Ryser, Brualdi, and Stein 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 Aharoni, Kotlar, and Ziv 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 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 $\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.

Détail

DOI : 10.37236/5246

Classification : 05C70, 05C15, 05B15, 05D15
Mots-clés : matchings, connectedness, Latin squares, transversals