{
  "id": "2110.10445",
  "version": "v3",
  "published": "2021-10-20T09:20:25.000Z",
  "updated": "2022-03-25T02:41:18.000Z",
  "title": "Note on the Polyhedral Description of the Minkowski Sum of Two L-convex Sets",
  "authors": [
    "Satoko Moriguchi",
    "Kazuo Murota"
  ],
  "comment": "36 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "L-convex sets are one of the most fundamental concepts in discrete convex analysis. Furthermore, the Minkowski sum of two L-convex sets, called L2-convex sets, is an intriguing object that is closely related to polymatroid intersection. This paper reveals the polyhedral description of an L2-convex set, together with the observation that the convex hull of an L2-convex set is a box-TDI polyhedron. Two different proofs are given for the polyhedral description. The first is a structural short proof, relying on the conjugacy theorem in discrete convex analysis, and the second is a direct algebraic proof, based on Fourier-Motzkin elimination. The obtained results admit natural graph representations. Implications of the obtained results in discrete convex analysis are also discussed.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2022-03-25T02:41:18.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "52A41",
      "90C27",
      "90C25"
    ],
    "keywords": [
      "polyhedral description",
      "l-convex sets",
      "minkowski sum",
      "discrete convex analysis",
      "l2-convex set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 36,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}