Basis problems for Borel graphs

Abstract

Following [12], we examine dichotomies about graphs defined on standard Borel spaces in which the edge relation is also Borel. More precisely, we study the Borel homomorphisms between such graphs and the corresponding notion of Borel chromatic number. It turns out that this category enjoys structural results not present in the category of all graphs. In particular, the concept of Borel chromatic number frequently does not coincide with the concept of the usual chromatic number. Cases of special interest are provided by graphs defined by the shift operation. We also brie y analyze graphs defined on families of finite sets of natural numbers.