Borel Chromatic Numbers

✍ Scribed by A.S Kechris; S Solecki; S Todorcevic

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 342 KB
• Volume: 141
• Category: Article
• ISSN: 0001-8708
• DOI: 10.1006/aima.1998.1771

✦ Synopsis

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 + 0 , is a Borel map c: X Ä Y with card(Y)=n, such that xRy O c(x){c( y). If such a Borel coloring exists we define the Borel chromatic number of G, in symbols / B (G), to be the smallest such n. Otherwise we say that G has uncountable Borel chromatic number, in symbols / B (G)>+ 0 .

In Section 3 we discuss several interesting examples of Borel graphs G for which the usual chromatic number /(G) is small while its Borel chromatic number / B (G) is large. For instance, there are examples of Borel graphs G