Borel chromatic numbers (Q1279827)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Borel chromatic numbers
scientific article

    Statements

    Borel chromatic numbers (English)
    0 references
    19 August 1999
    0 references
    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\).
    0 references
    0 references
    Borel space
    0 references
    Borel sets
    0 references
    Borel coloring
    0 references
    Borel chromatic number
    0 references
    uncountable Borel number
    0 references
    Borel graphs
    0 references
    Borel function
    0 references
    0 references
    0 references
    0 references
    0 references