Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-17T05:32:08.636Z Has data issue: false hasContentIssue false

JUMP OPERATIONS FOR BOREL GRAPHS

Published online by Cambridge University Press:  01 May 2018

ADAM R. DAY
Affiliation:
SCHOOL OF MATHEMATICS, STATISTICS AND OPERATIONS RESEARCH VICTORIA UNIVERSITY OF WELLINGTON WELLINGTON, NEW ZEALAND E-mail: adam.day@vuw.ac.nz
ANDREW S. MARKS
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF CALIFORNIA, LOS ANGELES LOS ANGELES, CA, USA E-mail: marks@math.ucla.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 nonseparation result for iterated Fréchet 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.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2018