{
  "id": "1403.0920",
  "version": "v2",
  "published": "2014-03-04T19:54:03.000Z",
  "updated": "2016-02-03T14:16:28.000Z",
  "title": "Matroids, Delta-matroids and Embedded Graphs",
  "authors": [
    "Carolyn Chun",
    "Iain Moffatt",
    "Steven D. Noble",
    "Ralf Rueckriemen"
  ],
  "comment": "We have split this paper into two. The later material of version 1 now appears in \"On the interplay between embedded graphs and delta-matroids\". Some new results have been added",
  "categories": [
    "math.CO"
  ],
  "abstract": "Matroid theory is often thought of as a generalization of graph theory. In this paper we propose an analogous correspondence between embedded graphs and delta-matroids. We show that delta-matroids arise as the natural extension of graphic matroids to the setting of embedded graphs. We show that various basic ribbon graph operations and concepts have delta-matroid analogues, and illustrate how the connections between embedded graphs and delta-matroids can be exploited. Also, in direct analogy with the fact that The Tutte polynomial is matroidal, we show that several polynomials of embedded graphs from the literature, including the Las Vergnas, Bollabas-Riordan and Krushkal polynomials, are in fact delta-matroidal.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-03-04T19:54:03.000Z",
      "abstract": "Matroid theory is often thought of as a generalization of graph theory. In this paper we propose an analogous correspondence between embedded graphs and delta-matroids. We show that delta-matroids arise as the natural extension of graphic matroids to the setting of embedded graphs. We illustrate how the connections between embedded graphs and delta-matroids can be exploited by using these connections to find an excluded minor characterization and a rough structure theorem for the class of delta-matroids that arise as twists of matroids. Also, we show that several polynomials of embedded graphs, including the Bollob\\'as-Riordan, Penrose, and transition polynomials, are in fact delta-matroidal.",
      "comment": null,
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2016-02-03T14:16:28.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "embedded graphs",
      "rough structure theorem",
      "fact delta-matroidal",
      "transition polynomials",
      "connections"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1403.0920C"
    }
  }
}