# Lattice Structure for Orientations of Graphs

“Lattice Structure for Orientations of Graphs” (2025), by Jim Propp. Mathematics research paper. Original abstract below, unchanged. A free PDF is available.

- Authors: Jim Propp
- Published: November 3, 2025
- Field: Mathematics
- DOI: https://doi.org/10.37236/9474
- Free PDF: https://arxiv.org/pdf/math/0209005

## 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.

Canonical page: https://nerdi.pages.dev/paper/W170254964
Read three real papers a day in Nerdi (iPhone): https://apps.apple.com/app/apple-store/id6813826387?pt=128757794&ct=web-paper&mt=8