A dichotomy characterizing analytic digraphs of uncountable Borel chromatic number in any dimension

Lecomte, Dominique

doi:10.1090/S0002-9947-09-04792-8

A dichotomy characterizing analytic digraphs of uncountable Borel chromatic number in any dimension
HTML articles powered by AMS MathViewer

by Dominique Lecomte PDF

Trans. Amer. Math. Soc. 361 (2009), 4181-4193 Request permission

Abstract:

We study the extension of the Kechris-Solecki-Todorčević dichoto-my on analytic graphs to dimensions higher than 2. We prove that the extension is possible in any dimension, finite or infinite. The original proof works in the case of the finite dimension. We first prove that the natural extension does not work in the case of the infinite dimension, for the notion of continuous homomorphism used in the original theorem. Then we solve the problem in the case of the infinite dimension. Finally, we prove that the natural extension works in the case of the infinite dimension, but for the notion of Baire-measurable homomorphism.

References

Béla Bollobás, Modern graph theory, Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, 1998. MR 1633290, DOI 10.1007/978-1-4612-0619-4
L. A. Harrington, A. S. Kechris, and A. Louveau, A Glimm-Effros dichotomy for Borel equivalence relations, J. Amer. Math. Soc. 3 (1990), no. 4, 903–928. MR 1057041, DOI 10.1090/S0894-0347-1990-1057041-5
Alexander S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995. MR 1321597, DOI 10.1007/978-1-4612-4190-4
A. S. Kechris, S. Solecki, and S. Todorcevic, Borel chromatic numbers, Adv. Math. 141 (1999), no. 1, 1–44. MR 1667145, DOI 10.1006/aima.1998.1771
Yiannis N. Moschovakis, Descriptive set theory, Studies in Logic and the Foundations of Mathematics, vol. 100, North-Holland Publishing Co., Amsterdam-New York, 1980. MR 561709
Gerald E. Sacks, Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR 1080970, DOI 10.1007/BFb0086109