{
  "id": "2408.17067",
  "version": "v1",
  "published": "2024-08-30T07:50:51.000Z",
  "updated": "2024-08-30T07:50:51.000Z",
  "title": "Stable matchings, choice functions, and linear orders",
  "authors": [
    "Alexander V. Karzanov"
  ],
  "comment": "28 pages, in Russian language",
  "categories": [
    "math.CO"
  ],
  "abstract": "We consider a model of stable edge sets (``matchings'') in a bipartite graph $G=(V,E)$ in which the preferences for vertices of one side (``firms'') are given via choice functions subject to standard axioms of consistence, substitutability and cardinal monotonicity, whereas the preferences for the vertices of the other side (``workers') via linear orders. For such a model, we present a combinatorial description of the structure of rotations and develop an algorithm to construct the poset of rotations, in time $O(|E|^2)$ (including oracle calls). As a consequence, one can obtain a ``compact'' affine representation of stable matchings and efficiently solve some related problems. (The paper is written in Russian.)",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-08-30T07:50:51.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "91C02",
      "91C78"
    ],
    "keywords": [
      "linear orders",
      "stable matchings",
      "choice functions subject",
      "bipartite graph",
      "affine representation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 28,
      "language": "ru",
      "license": "arXiv",
      "status": "editable"
    }
  }
}