{
  "id": "math/0209005",
  "version": "v2",
  "published": "2002-09-01T07:13:02.000Z",
  "updated": "2020-05-26T21:14:38.000Z",
  "title": "Lattice structure for orientations of graphs",
  "authors": [
    "James Propp"
  ],
  "comment": "37 pages, 20 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "Earlier researchers have studied the set of orientations of a connected finite graph $G$, and have shown that any two such orientations having the same flow-difference around all closed loops can be obtained from one another by a succession of local moves of a simple type. Here I show that the set of orientations of $G$ having the same flow-differences around all closed loops can be given the structure of a distributive lattice. The construction generalizes partial orderings that arise in the study of alternating sign matrices. It also gives rise to lattices for the set of degree-constrained factors of a bipartite planar graph; as special cases, one obtains lattices that arise in the study of plane partitions and domino tilings. Lastly, the theory gives a lattice structure to the set of spanning trees of a planar graph.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2002-09-01T07:13:02.000Z",
      "comment": "50 pages, 20 figures (at end)",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2020-05-26T21:14:38.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A99",
      "06A99"
    ],
    "keywords": [
      "lattice structure",
      "orientations",
      "construction generalizes partial orderings",
      "closed loops",
      "bipartite planar graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 37,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2002math......9005P"
    }
  }
}