Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-07T12:55:58.623Z 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)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

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

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