Borel chromatic numbers (Q1279827): Difference between revisions

From the article: We consider graphs \({\mathcal G}=(X,R)\) where the vertex set \(X\) is a standard Borel space (i.e., a complete separable metrizable space equipped with its \(\sigma\)-algebra of Borel sets), and the edge relation \(R\subseteq X^2\) is ``definable,'' i.e., Borel, analytic, coanalytic, etc. A Borel \(n\)-coloring of such a graph, where \(1\leq n\leq\aleph_0\), is a Borel map \(c:X\to Y\) with \(\text{card}(Y)=n\), such that \(xRy\Rightarrow c(x)\neq c(y)\). If such a Borel coloring exists we define the Borel chromatic number of \({\mathcal G}\), in symbols \(\chi_B({\mathcal G})\), to be the smallest such \(n\). Otherwise we say that \({\mathcal G}\) has uncountable Borel number, in symbols \(\chi_B({\mathcal G})>\aleph_0\). The many areas investigated include: examples of Borel graphs \({\mathcal G}\) for which the usual chromatic number \(\chi({\mathcal G})\) is small while its Borel chromatic number \(\chi_B({\mathcal G})\) is large; a complete analysis of the situation in which \(\chi_B({\mathcal G})>\aleph_0\); showing that in the case of the graph \({\mathcal G}_F\) generated by a single Borel function \(F\), \(\chi_B({\mathcal G})\) takes on the values and only the values 1, 2, 3, and \(\aleph_0\). Some open problems are posed, e.g., the authors ask for examples, if any, of acyclic Borel graphs \({\mathcal G}\) satisfying \(3<\chi_B({\mathcal G})<\aleph_0\).