Two dichotomy theorems on colourability of non-analytic graphs

Vladimir Kanovei

Fundamenta Mathematicae (1997)

  • Volume: 154, Issue: 2, page 183-201
  • ISSN: 0016-2736

Abstract

top
We prove:  Theorem 1. Let κ be an uncountable cardinal. Every κ-Suslin graph G on reals satisfies one of the following two requirements: (I) G admits a κ-Borel colouring by ordinals below κ; (II) there exists a continuous homomorphism (in some cases an embedding) of a certain locally countable Borel graph G 0 into G.  Theorem 2. In the Solovay model, every OD graph G on reals satisfies one of the following two requirements: (I) G admits an OD colouring by countable ordinals; (II) as above.

How to cite

top

Kanovei, Vladimir. "Two dichotomy theorems on colourability of non-analytic graphs." Fundamenta Mathematicae 154.2 (1997): 183-201. <http://eudml.org/doc/212233>.

@article{Kanovei1997,
abstract = {We prove:  Theorem 1. Let κ be an uncountable cardinal. Every κ-Suslin graph G on reals satisfies one of the following two requirements: (I) G admits a κ-Borel colouring by ordinals below κ; (II) there exists a continuous homomorphism (in some cases an embedding) of a certain locally countable Borel graph $G_0$ into G.  Theorem 2. In the Solovay model, every OD graph G on reals satisfies one of the following two requirements: (I) G admits an OD colouring by countable ordinals; (II) as above.},
author = {Kanovei, Vladimir},
journal = {Fundamenta Mathematicae},
keywords = {graph on reals; acyclic graph; locally thin graph; Borel colouring; definable colouring; dichotomies},
language = {eng},
number = {2},
pages = {183-201},
title = {Two dichotomy theorems on colourability of non-analytic graphs},
url = {http://eudml.org/doc/212233},
volume = {154},
year = {1997},
}

TY - JOUR
AU - Kanovei, Vladimir
TI - Two dichotomy theorems on colourability of non-analytic graphs
JO - Fundamenta Mathematicae
PY - 1997
VL - 154
IS - 2
SP - 183
EP - 201
AB - We prove:  Theorem 1. Let κ be an uncountable cardinal. Every κ-Suslin graph G on reals satisfies one of the following two requirements: (I) G admits a κ-Borel colouring by ordinals below κ; (II) there exists a continuous homomorphism (in some cases an embedding) of a certain locally countable Borel graph $G_0$ into G.  Theorem 2. In the Solovay model, every OD graph G on reals satisfies one of the following two requirements: (I) G admits an OD colouring by countable ordinals; (II) as above.
LA - eng
KW - graph on reals; acyclic graph; locally thin graph; Borel colouring; definable colouring; dichotomies
UR - http://eudml.org/doc/212233
ER -

References

top
  1. [1] D. Guaspari, Trees, norms, and scales, in: London Math. Soc. Lecture Note Ser. 87, Cambridge Univ. Press, 1983, 135-161. Zbl0549.03040
  2. [2] L. A. Harrington, A. S. Kechris and A. Louveau, A Glimm-Effros dichotomy for Borel equivalence relations, J. Amer. Math. Soc. 3 (1990), 903-928. Zbl0778.28011
  3. [3] L. A. Harrington and S. Shelah, Counting equivalence classes for co-κ-Souslin equivalence relations, in: D. van Dalen et al. (eds.), Logic Colloquium '80 (Prague, 1980), North-Holland, 1982, 147-152. 
  4. [4] G. Hjorth, Thin equivalence relations and effective decompositions, J. Symbolic Logic 58 (1993), 1153-1164. Zbl0793.03051
  5. [5] G. Hjorth, A remark on ∏ 1 1 equivalence relations, handwritten note. 
  6. [6] V. Kanovei, An Ulm-type classification theorem for equivalence relations in Solovay model, J. Symbolic Logic, to appear. Zbl0895.03020
  7. [7] V. Kanovei, On a dichotomy related to colourings of definable graphs in generic models, preprint ML-96-10, University of Amsterdam, 1996. 
  8. [8] A. S. Kechris, Classical Descriptive Set Theory, Springer, 1995. 
  9. [9] A. S. Kechris, S. Solecki and S. Todorčević, Borel chromatic numbers, Adv. Math., to appear. Zbl0100.24105
  10. [10] R. M. Solovay, A model of set theory in which every set of reals is Lebesgue measurable, Ann. of Math. 92 (1970), 1-56. Zbl0207.00905

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.