PDF

Discussiones Mathematicae General Algebra and Applications 24(1) (2004) 95-114
DOI: https://doi.org/10.7151/dmgaa.1078

ON INTERVAL DECOMPOSITION LATTICES

Stephan Foldes Institute of Mathematics Tampere University of Technology 33101 Tampere, Finland e-mail: stephan.foldes@tut.fi

Sándor Radeleczki Institute of Mathematics University of Miskolc 3515 Miskolc-Egyetemváros, Hungary e-mail: matradi@gold.uni-miskolc.hu

Abstract

Intervals in binary or n-ary relations or other discrete structures generalize the concept of interval in an ordered set. They are defined abstractly as closed sets of a closure system on a set V, satisfying certain axioms. Decompositions are partitions of V whose blocks are intervals, and they form an algebraic semimodular lattice. Lattice-theoretical properties of decompositions are explored, and connections with particular types of intervals are established.

Keywords: interval, closure system, modular decomposition, semimodular lattice, partition lattice, strong set, lexicographic sum.

2000 Mathematics Subject Classification: Primary 06B05, 06A15, 06C10, 08A02; Secondary 05C99, 03C99.

References

[1]	H. Bachmann, Transfinite Zahlen, Springer-Verlag, Berlin 1967.
[2]	A. Bastiani, Théorie des Ensembles, Centre de Documentation Universitaire, Paris 1970.
[3]	P. Crawley and R.P. Dilworth, Algebraic Theory of Lattices, Prentice-Hall Inc., Englewood Cliffs, NJ, 1973.
[4]	W. Dörfler, Ueber die X-Summe von gerichteten Graphen, Arch. Math. 22 (1971), 24-36.
[5]	W. Dörfler and W. Imrich, Über die X-Summe von Mengensystemen, p. 297-309 in: Colloq. Soc. Math. J. Bolyai, vol. 4 (``Combinatorial Theory and its Applications, I.''), North-Holland, Amsterdam 1970.
[6]	S. Foldes, Relation denses et dispersées: généralisation d'un théorème de Hausdorff, C.R. Acad. Sc. Paris A 277 (1973), 269-271.
[7]	S. Foldes, On intervals in relational structures, Z. Math. Logik Grundlag. Math. 26 (1980), 97-101.
[8]	S. Foldes, Lexicographic sums of ordered sets and hypergroupoids, p. 97-101 in: ``Algebraic Hyperstructures and Applications'', World Scientific Publ., Teaneck, NJ, 1991.
[9]	R. Fraissé, Course of Mathematical Logic, Vol. I, Reidel, Dordrecht 1973.
[10]	R. Fraissé, Present problems about intervals in relation theory and logic, p. 179-200 in: ``Non-classical Logics, Model theory and Computability'', North-Holland, Amsterdam 1977.
[11]	R. Fraissé, Theory of Relations, Revised Edition, Elsevier, Amsterdam 2000.
[12]	T. Gallai, Transitiv orientierbare graphen, Acta Math. Acad. Sci. Hungar. 18 (1967), 25-66.
[13]	D.W.H. Gillam, A concrete representation theorem for intervals of multirelations, Z. Math. Logik Grundlag. Math. 24 (1978), 463-466.
[14]	A. Gleyzal, Order types and structure of orders, Trans. Amer. Math. Soc. 48 (1950), 451-466.
[15]	G. Grätzer, General Lattice Theory, Academic Press, New York 1978.
[16]	M. Habib and M.C. Maurer, On X-join decomposition for undirected graphs, Discrete Appl. Math. 1 (1979), 201-207.
[17]	F. Hausdorff, Grundzüge der Mengenlehre, Veit u. Co., Leipzig 1914, reprinted Chelsea, New York 1949.
[18]	F. Hausdorff, Grundzüge einer Theorie der geordneten Mengen, Math. Ann. 65 (1918), 435-505.
[19]	P. Ille, L'intervalle relationnel et ses généralisations, C.R. Acad. Sc. Paris Ser. I Math. 306 (1988), 1-4.
[20]	P. Ille, Clôture intervallaire et extension logique d'une relation, Z. Math. Logik Grundlag. Math. 36 (1990), 217-227.
[21]	P. Ille, L'ensemble des intervalles d'une multirelation binaire et reflexive, Z. Math. Logik Grundlag. Math. 37 (1991), 227-256.
[23]	R.M. McConnell and J.P. Spinrad, Modular decomposition and transitive orientation, Discrete Math. 201 (1999), 189-241.
[24]	R.H. Möhring, Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and Boolean functions, Ann. Oper. Res. 4 (1985), 195-225.
[25]	R.H. Möhring and F.J. Radermacher, Substitution decomposition of discrete structures and connections to combinatorial optimization, Ann. Discrete Math. 19 (1984), 257-355.
[26]	G. Sabidussi, Graph derivatives, Math. Zeitschrift 76 (1961), 385-401.
[27]	B.S.W. Schröder, Ordered Sets. An Introduction, Birkhäuser, Basel 2002.
[28]	M. Stern, Semimodular Lattices, Theory and Applications, Cambridge University Press, Cambridge 1999.
[29]	W.T. Trotter, Combinatorics and Partially Ordered Sets. Dimension Theory, Johns Hopkins University Press, Baltimore, MD, 1992.
[30]	I. Zverovich, Extension of hereditary classes with substitutions, Discrete Appl. Math. 128 (2003), 487-509.

Received 26 November 2003
Revised 13 June 2004