{
  "id": "2404.09347",
  "version": "v1",
  "published": "2024-04-14T20:08:26.000Z",
  "updated": "2024-04-14T20:08:26.000Z",
  "title": "Matroid variant of Matiyasevich formula and its application",
  "authors": [
    "E. Yu. Lerner"
  ],
  "comment": "16 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "In 1977, Yu.V. Matiyasevich proposed a formula expressing the chromatic polynomial of an arbitrary graph as a linear combination of flow polynomials of subgraphs of the original graph. In this paper, we prove that this representation is a particular case of one (easily verifiable) formula, namely, the representation of the characteristic polynomial of an arbitrary matroid as a linear combination of characteristic polynomials of dual matroids. As applications, we consider an explicit expression for the flow polynomial of a complete graph and a formula for the characteristic polynomial of the matroid dual to the matroid of the projective geometry over a finite field. We prove, in particular, that their major coefficients are defined by the beginning of a certain row in the Pascal triangle. We study in detail the connection with convolution formulas and other results for Tutte polynomials.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-04-14T20:08:26.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05B35",
      "05C31",
      "05B25"
    ],
    "keywords": [
      "matroid variant",
      "matiyasevich formula",
      "characteristic polynomial",
      "application",
      "linear combination"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}