{
  "id": "2012.14992",
  "version": "v1",
  "published": "2020-12-30T00:55:59.000Z",
  "updated": "2020-12-30T00:55:59.000Z",
  "title": "On the Aharoni-Berger conjecture for general graphs",
  "authors": [
    "Ron Aharoni",
    "Eli Berger",
    "Maria Chudnovsky",
    "Shira Zerbib"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A conjecture of the first two authors is that $n$ matchings of size $n$ in any graph have a rainbow matching of size $n-1$. There are quite a few asymptotic results, but one problem remains obstinate: prove that $n$ matchings of size $n$ have a rainbow matching of size $n-o(n)$. This is known when the graph if bipartite, and when the matchings are disjoint. We prove a lower bound of $\\frac{2}{3}n-1$, improving on the trivial $\\frac{1}{2}n$, and an analogous result for hypergraphs. For $\\{C_3,C_5\\}$-free graphs and for disjoint matchings we obtain a lower bound of $\\frac{3n}{4}-O(1)$. We also prove a result on rainbow paths, that if extended to alternating paths would prove the $n-o(n)$ conjecture.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-12-30T00:55:59.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "general graphs",
      "aharoni-berger conjecture",
      "lower bound",
      "problem remains obstinate",
      "rainbow matching"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}