{
  "id": "1601.00943",
  "version": "v1",
  "published": "2016-01-05T19:27:36.000Z",
  "updated": "2016-01-05T19:27:36.000Z",
  "title": "Representation of large matchings in bipartite graphs",
  "authors": [
    "Ron Aharoni",
    "Dani Kotlar",
    "Ran Ziv"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $f(n)$ be the smallest number such that every collection of $n$ matchings, each of size at least $f(n)$, in a bipartite graph, has a full rainbow matching. Generalizing famous conjectures of Ryser, Brualdi and Stein, Aharoni and Berger conjectured that $f(n)=n+1$ for every $n>1$. Clemens and Ehrenm{\\\"u}ller proved that $f(n) \\le \\frac{3}{2}n +o(n)$. We show that the $o(n)$ term can be reduced to a constant, namely $f(n) \\le \\lceil \\frac{3}{2}n \\rceil+1$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-01-05T19:27:36.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bipartite graph",
      "large matchings",
      "representation",
      "smallest number",
      "full rainbow matching"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160100943A"
    }
  }
}