Three-and-more set theorems

Pavol Hell; Jaroslav Nešetřil; André Raspaud; Eric Sopena

Commentationes Mathematicae Universitatis Carolinae (2000)

  • Volume: 41, Issue: 4, page 793-801
  • ISSN: 0010-2628

Abstract

top
In this paper we generalize classical 3-set theorem related to stable partitions of arbitrary mappings due to Erdős-de Bruijn, Katětov and Kasteleyn. We consider a structural generalization of this result to partitions preserving sets of inequalities and characterize all finite sets of such inequalities which can be preserved by a “small” coloring. These results are also related to graph homomorphisms and (oriented) colorings.

How to cite

top

Hell, Pavol, et al. "Three-and-more set theorems." Commentationes Mathematicae Universitatis Carolinae 41.4 (2000): 793-801. <http://eudml.org/doc/248638>.

@article{Hell2000,
abstract = {In this paper we generalize classical 3-set theorem related to stable partitions of arbitrary mappings due to Erdős-de Bruijn, Katětov and Kasteleyn. We consider a structural generalization of this result to partitions preserving sets of inequalities and characterize all finite sets of such inequalities which can be preserved by a “small” coloring. These results are also related to graph homomorphisms and (oriented) colorings.},
author = {Hell, Pavol, Nešetřil, Jaroslav, Raspaud, André, Sopena, Eric},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {relation; compactness; combinatorics of mappings; relation; homomorphism},
language = {eng},
number = {4},
pages = {793-801},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Three-and-more set theorems},
url = {http://eudml.org/doc/248638},
volume = {41},
year = {2000},
}

TY - JOUR
AU - Hell, Pavol
AU - Nešetřil, Jaroslav
AU - Raspaud, André
AU - Sopena, Eric
TI - Three-and-more set theorems
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2000
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 41
IS - 4
SP - 793
EP - 801
AB - In this paper we generalize classical 3-set theorem related to stable partitions of arbitrary mappings due to Erdős-de Bruijn, Katětov and Kasteleyn. We consider a structural generalization of this result to partitions preserving sets of inequalities and characterize all finite sets of such inequalities which can be preserved by a “small” coloring. These results are also related to graph homomorphisms and (oriented) colorings.
LA - eng
KW - relation; compactness; combinatorics of mappings; relation; homomorphism
UR - http://eudml.org/doc/248638
ER -

References

top
  1. Abramovich Y.A., Arenson E.L., Kitover A., Banach C(K)-modules and operations preserving disjointness, Berkeley Report no. MSRI 05808-91 (1991). MR1202880
  2. de Bruijn N.G., Erdös P., A colour problem for infinite graphs and a problem in the theory of relations, Indagationes Math. 13 (1951), 371-373. (1951) MR0046630
  3. Dreyer P., Malon Ch., Nešetřil J., Universal H-colorable graphs without a given configuration, KAM-DIMATIA Series 99-428, Discrete Math., to appear. MR1905979
  4. Frolík Z., Fixed points of maps of β ( ℕ ) , Bull. Amer. Math. Soc. 74 (1968), 187-191. (1968) MR0222847
  5. Frolík Z., Fixed points of maps of extremally disconnected spaces and complete Boolean algebras, Bull. Acad. Polon. Sci. Ser. Sci. Math. Astronom. Phys. 16 (1968), 269-275. (1968) MR0233343
  6. Häggkvist R., Hell P., Universality of A -mote graphs, Europ. J. Combinatorics 14 (1993), 21-27. (1993) MR1197472
  7. Hell P., Nešetřil J., Oriented A-mote graphs, to appear. 
  8. Katětov M., A theorem on mappings, Comment. Math. Univ. Carolinae 8.3 (1967), 431-433. (1967) MR0229228
  9. Krawczyk A., Stepraǹs J., Continuous colorings of closed graphs, Topology Appl. 51 (1993), 13-26. (1993) MR1229497
  10. Nešetřil J., Sopena E., Vignal L., T-preserving homomorphisms of oriented graphs, Comment. Math. Univ. Carolinae 38.1 (1997), 125-136. (1997) MR1455476
  11. Pérennes S., A proof of Jean de Rumeur's conjecture, Discrete Appl. Math. 74 3 295-299 (1997). (1997) Zbl0869.05035MR1444947
  12. Rumeur J., Communications dans les réseaux de processeurs, Masson, 1994. 

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.