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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.