{
  "id": "2002.01001",
  "version": "v1",
  "published": "2020-02-03T20:21:52.000Z",
  "updated": "2020-02-03T20:21:52.000Z",
  "title": "The lattice of cycles of an undirected graph",
  "authors": [
    "Gennadiy Averkov",
    "Anastasia Chavez",
    "Jesus A. De Loera",
    "Bryan R. Gillespie"
  ],
  "comment": "18 pages, 0 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "We study bases of the lattice generated by the cycles of an undirected graph, defined as the integer linear combinations of the 0/1-incidence vectors of cycles. We prove structural results for this lattice, including explicit formulas for its dimension and determinant, and we present efficient algorithms to construct lattice bases, using only cycles as generators, in quadratic time. By algebraic considerations, we relate these results to the more general setting with coefficients from an arbitrary Abelian group. Our results generalize old classical results for the vector space of cycles of a graph over the binary field to the case of an arbitrary field.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-02-03T20:21:52.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C50",
      "05C38",
      "52C07",
      "05C85",
      "68R10",
      "G.2.2"
    ],
    "keywords": [
      "undirected graph",
      "results generalize old classical results",
      "construct lattice bases",
      "integer linear combinations",
      "arbitrary abelian group"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}