Borel Chromatic Numbers

Abstract

We study in this paper graph coloring problems in the context of descriptive set theory. We consider graphs G=(X, R), where the vertex set X is a standard Borel space (i.e., a complete separable metrizable space equipped with its σ-algebra of Borel sets), and the edge relation R ⊆ X^2 is "definable", i.e., Borel, analytic, co-analytic, etc. A Borel n-coloring of such a graph, where 1⩽ n ⩽ N_0 , is a Borel map c: X → Y with card(Y)=n, such that xRy⇒c(x) ≠ {c( y). If such a Borel coloring exists we define the Borel chromatic number of G, in symbols X_B(G), to be the smallest such n. Otherwise we say that G has uncountable Borel chromatic number, in symbols X_B(G) > N_0.