Jump operations for Borel graphs

Borel graph coloring Borel graph combinatorics descriptive set theory effective descriptive set theory Friedman-Stanley jump Fréchet ideals graph homomorphism

Mathematics Subject Classification ID

Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Descriptive set theory (03E15)

Abstract: We investigate the class of bipartite Borel graphs organized by the order of Borel homomorphism. We show that this class is unbounded by finding a jump operator for Borel graphs analogous to a jump operator of Louveau for Borel equivalence relations. The proof relies on a non-separation result for iterated Frechet ideals and filters due to Debs and Saint Raymond. We give a new proof of this fact using effective descriptive set theory. We also investigate an analogue of the Friedman-Stanley jump for Borel graphs. This analogue does not yield a jump operator for bipartite Borel graphs. However, we use it to answer a question of Kechris and Marks by showing that there is a Borel graph with no Borel homomorphism to a locally countable Borel graph, but each of whose connected components has a countable Borel coloring.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Jump operations for Borel graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4638971)