Hostname: page-component-8448b6f56d-qsmjn Total loading time: 0 Render date: 2024-04-19T16:46:34.477Z Has data issue: false hasContentIssue false
  • English
  • Français

ULD-Lattices and Δ-Bonds

Published online by Cambridge University Press:  01 September 2009

STEFAN FELSNER  and
KOLJA B. KNAUER
STEFAN FELSNER
Affiliation:
Institut für Mathematik, Technische Universität Berlin, Germany (e-mail: felsner@math.tu-berlin.de, knauer@math.tu-berlin.de)
KOLJA B. KNAUER
Affiliation:
Institut für Mathematik, Technische Universität Berlin, Germany (e-mail: felsner@math.tu-berlin.de, knauer@math.tu-berlin.de)
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 18 , Issue 5: New Directions in Algorithms, Combinatorics and Optimization , September 2009 , pp. 707 - 724
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Ardila, F. and Maneva, E. (2007) Pruning processes and a new characterization of convex geometries. Discrete Math. 309 3083–3091. arXiv:0706.3750v4[math.CO].Google Scholar
[2]Avann, S. P. (1968) Locally atomic upper locally distributive lattices. Math. Ann. 175 320–336.Google Scholar
[3]Birkhoff, G. and Bennett, M. K. (1985) The convexity lattice of a poset. Order 2 223–242.CrossRefGoogle Scholar
[4]Bjorner, A. (1980) Shellable and Cohen–Macaulay partially ordered sets. Trans. Amer. Math. Soc. 260 159–183.Google Scholar
[5]Bjorner, A. and Lovasz, L. (1992) Chip-firing games on directed graphs. J. Algebraic Combin. 1 305–328.Google Scholar
[6]Bjorner, A., Lovasz, L. and Shor, P. W. (1991) Chip-firing games on graphs. European J. Combin. 12 283–291.Google Scholar
[7]Bjorner, A. and Ziegler, G. M. (1992) Introduction to greedoids. In Matroid Applications, Vol. 40 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, pp. 284–357.Google Scholar
[8]Boulaye, G. (1967) Sous-arbres et homomorphismes à classes connexes dans un arbre. In Theory of Graphs International Symposium, pp. 47–50.Google Scholar
[9]Dilworth, R. P. (1940) Lattices with unique irreducible decompositions. Ann. of Math. 41 771–777.Google Scholar
[10]Dilworth, R. P. and Crawley, P. (1960) Decomposition theory for lattices without chain conditions. Trans. Amer. Math. Soc. 96 1–22.Google Scholar
[11]Edelman, P. H. (1980) Meet-distributive lattices and the antiexchange closure. Alg. Univ. 10 290–299.CrossRefGoogle Scholar
[12]Edelman, P. H. and Jamison, R. E. (1985) The theory of convex geometries. Geom. Dedicata 19 247–270.CrossRefGoogle Scholar
[13]Felsner, S. (2004) Lattice structures from planar graphs. Electron. J. Combin. 11 #15.Google Scholar
[14]Felsner, S. and Knauer, K. B. (2008) Distributive lattices, polyhedra, and generalized flow. arXiv:0811.1541v1[math.CO].Google Scholar
[15]Jamison, R. E. (1970) A development of axiomatic convexity. Clemson University Math. 48 15–20.Google Scholar
[16]Jamison, R. E. (1980) Copoints in antimatroïds. Congr. Numer. 29 534–544.Google Scholar
[17]Khuller, S., Naor, J. and Klein, P. (1993) The lattice structure of flow in planar graphs. SIAM J. Discrete Math. 6 477–490.Google Scholar
[18]Knauer, K. B. (2007) Partial orders on orientations via cycle flips. http://www.math.tu-berlin.de/~knauer/diplom.pdf.Google Scholar
[19]Korte, B. and Lovasz, L. (1984) Shelling structures, convexity and a happy end. In Graph Theory and Combinatorics (Cambridge 1983), Academic Press, London, pp. 219–232.Google Scholar
[20]Monjardet, B. (1990) The consequences of Dilworth's work on lattices with unique irreductible decompositions. In The Dilworth Theorems, Birkhäuser, pp. 192–201.CrossRefGoogle Scholar
[21]Nakamura, M. (2003) Excluded-minor characterizations of antimatroids arisen from posets and graph searches. Discrete Appl. Math. 129 487–498.Google Scholar
[22]Pfaltz, J. L. (1971) Convexity in directed graphs. J. Combin. Theory Ser. B 10 143–152.Google Scholar
[23]Propp, J. (1993) Lattice structure for orientations of graphs. arXiv:math/0209005v1[math.CO].Google Scholar
[24]Propp, J. (1997) Generating random elements of finite distributive lattices. Electron. J. Combin. 4 #15.CrossRefGoogle Scholar
[25]Propp, J. and Wilson, D. B. (1996) Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Struct. Alg. 9 223–252.3.0.CO;2-O>CrossRefGoogle Scholar
[26]Stern, M. (1999) Semimodular Lattices, Vol. 73 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge.CrossRefGoogle Scholar