# Two dichotomy theorems on colourability of non-analytic graphs

Fundamenta Mathematicae (1997)

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

## Access Full Article

top## Abstract

top## How to cite

topKanovei, 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] D. Guaspari, Trees, norms, and scales, in: London Math. Soc. Lecture Note Ser. 87, Cambridge Univ. Press, 1983, 135-161. Zbl0549.03040
- [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] 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] G. Hjorth, Thin equivalence relations and effective decompositions, J. Symbolic Logic 58 (1993), 1153-1164. Zbl0793.03051
- [5] G. Hjorth, A remark on ${\prod}_{1}^{1}$ equivalence relations, handwritten note.
- [6] V. Kanovei, An Ulm-type classification theorem for equivalence relations in Solovay model, J. Symbolic Logic, to appear. Zbl0895.03020
- [7] V. Kanovei, On a dichotomy related to colourings of definable graphs in generic models, preprint ML-96-10, University of Amsterdam, 1996.
- [8] A. S. Kechris, Classical Descriptive Set Theory, Springer, 1995.
- [9] A. S. Kechris, S. Solecki and S. Todorčević, Borel chromatic numbers, Adv. Math., to appear. Zbl0100.24105
- [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 ?

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