Measurable chromatic numbers. (English) Zbl 1157.03025

Summary: We show that if add(null) = \(\mathfrak c\), then the globally Baire and universally measurable chromatic numbers of the graph of any Borel function on a Polish space are equal and at most three. In particular, this holds for the graph of the unilateral shift on \([\mathbb N]^{\mathbb N}\), although its Borel chromatic number is \(\aleph _0\). We also show that if add(null) = \(\mathfrak c\), then the universally measurable chromatic number of every treeing of a measure amenable equivalence relation is at most three. In particular, this holds for “the” minimum analytic graph \(\mathcal G_0\) with uncountable Borel (and Baire measurable) chromatic number. In contrast, we show that for all \(\kappa \in \{ 2, 3, \ldots , \aleph _0, \mathfrak c \}\), there is a treeing of \(E_0\) with Borel and Baire measurable chromatic number \(\kappa \). Finally, we use a Glimm-Effros-style dichotomy theorem to show that every basis for a non-empty initial segment of the class of graphs of Borel functions of Borel chromatic number at least three contains a copy of \((\mathbb R^{<\mathbb N}, \supseteq )\).


03E15 Descriptive set theory
05C15 Coloring of graphs and hypergraphs
Full Text: DOI Link


[1] DOI: 10.1090/S0894-0347-1990-1057041-5 · doi:10.1090/S0894-0347-1990-1057041-5
[2] Israel Journal of Mathematics
[3] DOI: 10.1090/S0002-9947-1994-1149121-0 · doi:10.1090/S0002-9947-1994-1149121-0
[4] Transactions of the American Mathematical Society 281 pp 209– (1984) · doi:10.1090/S0002-9947-1984-0719666-7
[5] Measure and category (1971)
[6] Journal of the European Mathematical Society
[7] Ergodic Theory of Dynamic Systems
[8] Israel Journal of Mathematics
[9] DOI: 10.1016/0003-4843(70)90009-4 · Zbl 0222.02075 · doi:10.1016/0003-4843(70)90009-4
[10] DOI: 10.1007/s11856-008-0011-8 · Zbl 1140.37003 · doi:10.1007/s11856-008-0011-8
[11] DOI: 10.1006/aima.1998.1771 · Zbl 0918.05052 · doi:10.1006/aima.1998.1771
[12] Topics in orbit equivalence 1852 (2004)
[13] Classical descriptive set theory 156 (1995) · Zbl 0819.04002
[14] DOI: 10.1142/S0219061302000138 · Zbl 1008.03031 · doi:10.1142/S0219061302000138
[15] DOI: 10.1090/S0002-9939-98-04489-X · Zbl 0906.28008 · doi:10.1090/S0002-9939-98-04489-X
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.