On interval decomposition lattices

Stephan Foldes; Sándor Radeleczki

Discussiones Mathematicae - General Algebra and Applications (2004)

  • Volume: 24, Issue: 1, page 95-114
  • ISSN: 1509-9415

Abstract

top
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.

How to cite

top

Stephan Foldes, and Sándor Radeleczki. "On interval decomposition lattices." Discussiones Mathematicae - General Algebra and Applications 24.1 (2004): 95-114. <http://eudml.org/doc/287689>.

@article{StephanFoldes2004,
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.},
author = {Stephan Foldes, Sándor Radeleczki},
journal = {Discussiones Mathematicae - General Algebra and Applications},
keywords = {interval; closure system; modular decomposition; semimodular lattice; partition lattice; strong set; lexicographic sum; intervals in relations},
language = {eng},
number = {1},
pages = {95-114},
title = {On interval decomposition lattices},
url = {http://eudml.org/doc/287689},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Stephan Foldes
AU - Sándor Radeleczki
TI - On interval decomposition lattices
JO - Discussiones Mathematicae - General Algebra and Applications
PY - 2004
VL - 24
IS - 1
SP - 95
EP - 114
AB - 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.
LA - eng
KW - interval; closure system; modular decomposition; semimodular lattice; partition lattice; strong set; lexicographic sum; intervals in relations
UR - http://eudml.org/doc/287689
ER -

References

top
  1. [1] H. Bachmann, Transfinite Zahlen, Springer-Verlag, Berlin 1967. 
  2. [2] A. Bastiani, Théorie des Ensembles, Centre de Documentation Universitaire, Paris 1970. 
  3. [3] P. Crawley and R.P. Dilworth, Algebraic Theory of Lattices, Prentice-Hall Inc., Englewood Cliffs, NJ, 1973. Zbl0494.06001
  4. [4] W. Dörfler, Ueber die X-Summe von gerichteten Graphen, Arch. Math. 22 (1971), 24-36. Zbl0214.51202
  5. [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. [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. Zbl0268.04002
  7. [7] S. Foldes, On intervals in relational structures, Z. Math. Logik Grundlag. Math. 26 (1980), 97-101. Zbl0457.08001
  8. [8] S. Foldes, Lexicographic sums of ordered sets and hypergroupoids, 'Algebraic Hyperstructures and Applications', World Scientific Publ., Teaneck, NJ, 1991, 97-101. Zbl0745.20061
  9. [9] R. Fraissé, Course of Mathematical Logic, Vol. I, Reidel, Dordrecht 1973. 
  10. [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. [11] R. Fraissé, Theory of Relations, Revised Edition, Elsevier, Amsterdam 2000. Zbl0965.03059
  12. [12] T. Gallai, Transitiv orientierbare graphen, Acta Math. Acad. Sci. Hungar. 18 (1967), 25-66. Zbl0153.26002
  13. [13] D.W.H. Gillam, A concrete representation theorem for intervals of multirelations, Z. Math. Logik Grundlag. Math. 24 (1978), 463-466. Zbl0433.08003
  14. [14] A. Gleyzal, Order types and structure of orders, Trans. Amer. Math. Soc. 48 (1950), 451-466. Zbl0025.31001
  15. [15] G. Grätzer, General Lattice Theory, Academic Press, New York 1978. Zbl0436.06001
  16. [16] M. Habib and M.C. Maurer, On X-join decomposition for undirected graphs, Discrete Appl. Math. 1 (1979), 201-207. Zbl0439.05041
  17. [17] F. Hausdorff, Grundzüge der Mengenlehre, Veit u. Co., Leipzig 1914, reprinted Chelsea, New York 1949. 
  18. [18] F. Hausdorff, Grundzüge einer Theorie der geordneten Mengen, Math. Ann. 65 (1918), 435-505. Zbl39.0099.01
  19. [19] P. Ille, L'intervalle relationnel et ses généralisations, C.R. Acad. Sc. Paris Ser. I Math. 306 (1988), 1-4. Zbl0654.04001
  20. [20] P. Ille, Clôture intervallaire et extension logique d'une relation, Z. Math. Logik Grundlag. Math. 36 (1990), 217-227. Zbl0712.03027
  21. [21] P. Ille, L'ensemble des intervalles d'une multirelation binaire et reflexive, Z. Math. Logik Grundlag. Math. 37 (1991), 227-256. Zbl0742.04002
  22. [22] R.M. McConnell and J.P. Spinrad, Modular decomposition and transitive orientation, Discrete Math. 201 (1999), 189-241. Zbl0933.05146
  23. [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. [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. Zbl0567.90073
  25. [25] G. Sabidussi, Graph derivatives, Math. Zeitschrift 76 (1961), 385-401. Zbl0109.16404
  26. [26] B.S.W. Schröder, Ordered Sets. An Introduction, Birkhäuser, Basel 2002. 
  27. [27] M. Stern, Semimodular Lattices, Theory and Applications, Cambridge University Press, Cambridge 1999. Zbl0957.06008
  28. [28] W.T. Trotter, Combinatorics and Partially Ordered Sets. Dimension Theory, Johns Hopkins University Press, Baltimore, MD, 1992. Zbl0764.05001
  29. [29] I. Zverovich, Extension of hereditary classes with substitutions, Discrete Appl. Math. 128 (2003), 487-509. Zbl1021.05095

NotesEmbed ?

top

You must be logged in to post comments.