{
  "id": "1504.05373",
  "version": "v1",
  "published": "2015-04-21T10:20:28.000Z",
  "updated": "2015-04-21T10:20:28.000Z",
  "title": "Rainbow matchings and rainbow connectedness",
  "authors": [
    "Alexey Pokrovskiy"
  ],
  "comment": "17 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "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\\\"uller 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\\\"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 $\\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-04-21T10:20:28.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C70",
      "05C40",
      "05C20",
      "05B15",
      "05D15"
    ],
    "keywords": [
      "rainbow matching",
      "rainbow connectedness",
      "independent interest",
      "old conjectures",
      "latin squares"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150405373P"
    }
  }
}