Interval decomposition lattices are balanced. (English) Zbl 1352.06005

Summary: Intervals in binary or \(n\)-ary relations or other discrete structures generalize the concept of an interval in a linearly ordered set. They are defined abstractly as closed sets of a closure system on a set, satisfying certain axioms. Join-irreducible partitions into intervals are characterized in the lattice of all interval decompositions. This result is used to show that the lattice of interval decompositions is balanced, and the case when this lattice is distributive is also characterised.


06B05 Structure theory of lattices
06A15 Galois correspondences, closure operators (in relation to ordered sets)
06C10 Semimodular lattices, geometric lattices
Full Text: DOI arXiv


[1] P. Crawley, R. P. Dilworth, Algebraic Theory of Lattices, Prentice-Hall Inc., New Jersey, 1973. · Zbl 0494.06001
[2] G. Czédli, Factor lattices by tolerances, Acta Sci. Math. (Szeged) 44 (1982), 35-42. · Zbl 0484.06010
[3] W. Dörfler, Ueber die X-Summe von gerichteten Graphen, Arch. Math. 22 (1971), 24-36.
[4] W. Dörfler, W. Imrich, Ueber die X-Summe von Mengensystemen, In: “Combinatorial Theory and its Applications I.”, Colloq. Math. Soc. Janos Bolyai 10 (1973), Keszthely, Hungary, 1973, 261-383.
[5] S. Foldes, S. Radeleczki, On interval decomposition lattices, Discuss. Math. Gen. Algebra Appl. 24 (2004), 95-114. · Zbl 1062.06011
[6] R. Fraïssé, Course of Mathematical Logic, Vol. I, Reidel, Dordrecht, 1973.
[7] R. Fraïssé, Present problems about intervals in relation theory and logic, p. 179-200, in: “Non-classical Logics, Model Theory and Computability”, North-Holland, Amsterdam, 1977.
[8] R. Fraïssé, Theory of Relations, Revised Edition, Elsevier, 2000.
[9] T. Gallai, Transitiv orientierbare graphen, Acta Math. Acad. Sci. Hungar. 18 (1967), 25-66. · Zbl 0153.26002
[10] G. Grätzer, General Lattice Theory: Foundation, Birkhäuser/Springer, Basel, 2011.
[11] M. Habib, M. C. Maurer, On X-join decomposition for undirected graphs, Discrete Appl. Math. 1 (1979), 201-207. · Zbl 0439.05041
[12] F. Hausdorff, Grundzüge der Mengenlehre, Leipzig, 1914.
[13] F. Hausdorff, Grundzüge einer Theorie der geordneten Mengen, Math. Ann. 65 (1918), 435-505. · JFM 39.0099.01
[14] E. K. Horváth, S. Radeleczki, Notes on CD-independent subsets, Acta Sci. Math. (Szeged) 78 (2012), 3-24. · Zbl 1299.06002
[15] R. M. McConnell, J. P. Spinrad, Modular decomposition and transitive orientation, Discrete Math. 201 (1999), 189-241. · Zbl 0933.05146
[16] R. H. Möhring, Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and Boolean functions, Ann. Oper. Res. 4 (1985/6), 195-225.
[17] R. H. Möhring, F. J. Radermacher, Substitution decomposition of discrete structures and connections to combinatorial optimization, Ann. Discrete Math. 19 (1984), 257-355.
[18] S. Radeleczki, Maeda-type decomposition of CJ-generated algebraic lattices, Southeast Asian Bull. Math. 25 (2001), 503-513. · Zbl 1010.06007
[19] K. Reuter, The Kurosh-Ore exchange property, Acta Math. Hungar. 53 (1989), 119-127. · Zbl 0675.06003
[20] G. Sabidussi, Graph derivatives, Math. Z. 76 (1961), 385-401. · Zbl 0109.16404
[21] M. Stern, Semimodular Lattices, Theory and Applications, Cambridge University Press, 1999.
[22] A. Walendziak, Strongness in lattices, Demonstratio Math. 27 (1994), 569-572. · Zbl 0826.06003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.