Pokrovskiy, A; (2017) Rainbow matchings and rainbow connectedness. Electronic Journal of Combinatorics , 24 (1) , Article P1.13. 10.37236/5246.

Preview

Text Rainbow.pdf - Accepted Version Download (538kB) | Preview

Abstract

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¨aggkvist 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.

Download activity - last month

Export as JSONXMLCSV

Download activity - last 12 months

Export as JSONXMLCSV

Downloads by country - last 12 months

Export as XMLCSVJSON

Archive Staff Only

View Item