{
  "id": "1511.05775",
  "version": "v1",
  "published": "2015-11-18T13:46:44.000Z",
  "updated": "2015-11-18T13:46:44.000Z",
  "title": "Uniqueness of the extreme cases in theorems of Drisko and Erdős-Ginzburg-Ziv",
  "authors": [
    "Ron Aharoni",
    "Dani Kotlar",
    "Ran Ziv"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Drisko \\cite{drisko} proved (essentially) that every family of $2n-1$ matchings of size $n$ in a bipartite graph possesses a partial rainbow matching of size $n$. In \\cite{bgs} this was generalized as follows: Any $\\lfloor \\frac{k+2}{k+1} n \\rfloor -(k+1)$ matchings of size $n$ in a bipartite graph have a rainbow matching of size $n-k$. We extend this latter result to matchings of not necessarily equal cardinalities. Settling a conjecture of Drisko, we characterize those families of $2n-2$ matchings of size $n$ in a bipartite graph that do not possess a rainbow matching of size $n$. Combining this with an idea of Alon \\cite{alon}, we re-prove a characterization of the extreme case in a well-known theorem of Erd\\H{o}s-Ginzburg-Ziv in additive number theory.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-11-18T13:46:44.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "extreme case",
      "uniqueness",
      "erdős-ginzburg-ziv",
      "rainbow matching",
      "bipartite graph possesses"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv151105775A"
    }
  }
}