{
  "id": "2108.10502",
  "version": "v1",
  "published": "2021-08-24T03:19:38.000Z",
  "updated": "2021-08-24T03:19:38.000Z",
  "title": "Discrete Fenchel Duality for a Pair of Integrally Convex and Separable Convex Functions",
  "authors": [
    "Kazuo Murota",
    "Akihisa Tamura"
  ],
  "comment": "28 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Discrete Fenchel duality is one of the central issues in discrete convex analysis. The Fenchel-type min-max theorem for a pair of integer-valued M-natural-convex functions generalizes the min-max formulas for polymatroid intersection and valuated matroid intersection. In this paper we establish a Fenchel-type min-max formula for a pair of integer-valued integrally convex and separable convex functions. Integrally convex functions constitute a fundamental function class in discrete convex analysis, including both M-natural-convex functions and L-natural-convex functions, whereas separable convex functions are characterized as those functions which are both M-natural-convex and L-natural-convex. The theorem is proved by revealing a kind of box integrality of subgradients of an integer-valued integrally convex function. The proof is based on the Fourier-Motzkin elimination.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-08-24T03:19:38.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "52A41",
      "90C27",
      "90C25"
    ],
    "keywords": [
      "separable convex functions",
      "discrete fenchel duality",
      "discrete convex analysis",
      "integrally convex function",
      "integer-valued integrally convex"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 28,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}