Two dichotomy theorems on colourability of non-analytic graphs

Vladimir Kanovei

ArticleOriginal scientific text

Title

Two dichotomy theorems on colourability of non-analytic graphs

Authors ¹

Affiliations

Department of Mathematics, Moscow Transport Engineering Institute (MIIT), Obraztsova 15, Moscow 101475, Russia

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.

D. Guaspari, Trees, norms, and scales, in: London Math. Soc. Lecture Note Ser. 87, Cambridge Univ. Press, 1983, 135-161.
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.
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.
G. Hjorth, Thin equivalence relations and effective decompositions, J. Symbolic Logic 58 (1993), 1153-1164.
G. Hjorth, A remark on $\prod^{1}_1$ equivalence relations, handwritten note.
V. Kanovei, An Ulm-type classification theorem for equivalence relations in Solovay model, J. Symbolic Logic, to appear.
V. Kanovei, On a dichotomy related to colourings of definable graphs in generic models, preprint ML-96-10, University of Amsterdam, 1996.
A. S. Kechris, Classical Descriptive Set Theory, Springer, 1995.
A. S. Kechris, S. Solecki and S. Todorčević, Borel chromatic numbers, Adv. Math., to appear.
R. M. Solovay, A model of set theory in which every set of reals is Lebesgue measurable, Ann. of Math. 92 (1970), 1-56.

Title

Two dichotomy theorems on colourability of non-analytic graphs

Affiliations

Abstract

Bibliography