ULD-Lattices and Δ-Bonds
Stefan Felsner, Kolja Knauer · Combinatorics Probability Computing · 2009
We provide a characterization of upper locally distributive lattices (ULD-lattices) in terms of edge colourings of their cover graphs. In many instances where a set of combinatorial objects carries the order structure of a lattice, this characterization yields a slick proof of distributivity or UL-distributivity. This is exemplified by proving a distributive lattice structure on Δ-bonds with invariant circular flow-difference. This instance generalizes several previously studied lattice structures, in particular,c-orientations (Propp), α-orientations of planar graphs (Felsner, resp. de Mendez) and planar flows (Khuller, Naor and Klein). The characterization also applies to other instances,e.g., to chip-firing games.