Download PDF - On interval decomposition latticesAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

On interval decomposition lattices

Authors 1, 2

Affiliations

  1. Institute of Mathematics, Tampere University of Technology, 33101 Tampere, Finland
  2. Institute of Mathematics, University of Miskolc, 3515 Miskolc-Egyetemváros, Hungary

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

ENG
interval, closure system, modular decomposition, semimodular lattice, partition lattice, strong set, lexicographic sum

Bibliography

  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, Colloq. Soc. Math. J. Bolyai, vol. 4 ('Combinatorial Theory and its Applications, I.'), North-Holland, Amsterdam 1970, 297-309.
  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, 'Algebraic Hyperstructures and Applications', World Scientific Publ., Teaneck, NJ, 1991, 97-101.
  9. R. Fraissé, Course of Mathematical Logic, Vol. I, Reidel, Dordrecht 1973.
  10. R. Fraissé, Present problems about intervals in relation theory and logic, 'Non-classical Logics, Model theory and Computability', North-Holland, Amsterdam 1977, 179-200.
  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.
  22. R.M. McConnell and J.P. Spinrad, Modular decomposition and transitive orientation, Discrete Math. 201 (1999), 189-241.
  23. 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.
  24. 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.
  25. G. Sabidussi, Graph derivatives, Math. Zeitschrift 76 (1961), 385-401.
  26. B.S.W. Schröder, Ordered Sets. An Introduction, Birkhäuser, Basel 2002.
  27. M. Stern, Semimodular Lattices, Theory and Applications, Cambridge University Press, Cambridge 1999.
  28. W.T. Trotter, Combinatorics and Partially Ordered Sets. Dimension Theory, Johns Hopkins University Press, Baltimore, MD, 1992.
  29. I. Zverovich, Extension of hereditary classes with substitutions, Discrete Appl. Math. 128 (2003), 487-509.
Discussiones Mathematicae - General Algebra and Applications
2004/24/1
Export to PBN, Opens in new tab
Pages:
95-114
Main language of publication
English
Received
2003-11-26
Published
2004

DOI: 10.7151/dmgaa.1078

Exact and natural sciences