Lattice structure for orientations of graphs

Abstract

In 1986, Oliver Pretzel studied the set of orientations of a connected finite graph $G$ and showed 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. When the graph is drawn on the plane, a dual version of the construction puts a distributive lattice structure on the set of orientations of $G$ having the same indegrees at all vertices. In both settings, adjacent lattice-elements are related by simple local moves. This construction unifies earlier, similar constructions in combinatorics and statistical mechanics. It also gives rise to an interesting lattice structure on spanning trees. This article is an updated version of a preprint originally distributed in 1993.

41 pages, 20 figures

Cited by in corpus (26)

• Newton-Okounkov bodies, cluster duality, and mirror symmetry for Grassmannians
• The twist for positroid varieties
• Matching polytopes, toric geometry, and the non-negative part of the Grassmannian
• A compendium on the cluster algebra and quiver package in sage
• Cluster algebraic interpretation of infinite friezes
• Decomposition theorem on matchable distributive lattices
• Generalization of Schnyder woods to orientable surfaces and applications
• Remarks on Formal Knot Theory
• Distributive Lattices, Polyhedra, and Generalized Flow
• Determinant density and biperiodic alternating links
• Gale-Robinson quivers: from representations to combinatorial formulas
• Orientation-Constrained Rectangular Layouts
• Homological combinatorics and extensions of the cd-index
• Cluster algebras and binary subwords
• A geometric approach to acyclic orientations
• ULD-Lattices and Delta-Bonds
• First-return maps of Birkhoff sections of the geodesic flow
• An expansion formula for type A and Kronecker quantum cluster algebras
• Asymptotics of pure dimer coverings on rail-yard graphs
• An optimal algorithm to generate tilings
• Enumeration of paths and cycles and e-coefficients of incomparability graphs
• Morphisms and order ideals of toric posets
• Flips on homologous orientations of surface graphs with prescribed forbidden facial circuits
• Enumerating $k$-arc-connected orientations
• CAT-generation of ideals
• Domino tilings and related models: space of configurations of domains with holes