Lattice structure for orientations of graphs
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2002
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911209430712320 |
|---|---|
| author | Propp, James |
| author_facet | Propp, James |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_math_0209005 |
| institution | arXiv |
| publishDate | 2002 |
| record_format | arxiv |
| spellingShingle | Lattice structure for orientations of graphs Propp, James Combinatorics 05A99, 06A99 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. |
| title | Lattice structure for orientations of graphs |
| topic | Combinatorics 05A99, 06A99 |
| url | https://arxiv.org/abs/math/0209005 |