Geodesic
Lattice structure for orientations of graphs
The electronic journal of combinatorics, Tome 32 (2025) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/9474
Classification : 05C62, 05C10
Mots-clés : Thurston's definition of height functions, spanning trees 
@article{10_37236_9474,
     author = {Jim Propp},
     title = {Lattice structure for orientations of graphs},
     journal = {The electronic journal of combinatorics},
     year = {2025},
     volume = {32},
     number = {4},
     doi = {10.37236/9474},
     zbl = {8120112},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9474/}
}
TY  - JOUR
AU  - Jim Propp
TI  - Lattice structure for orientations of graphs
JO  - The electronic journal of combinatorics
PY  - 2025
VL  - 32
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9474/
DO  - 10.37236/9474
ID  - 10_37236_9474
ER  - 
%0 Journal Article
%A Jim Propp
%T Lattice structure for orientations of graphs
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/9474/
%R 10.37236/9474
%F 10_37236_9474
Jim Propp. Lattice structure for orientations of graphs. The electronic journal of combinatorics, Tome 32 (2025) no. 4. doi: 10.37236/9474

Cité par Sources :