Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-26T08:18:55.306Z Has data issue: false hasContentIssue false
  • English
  • Français

JUMP OPERATIONS FOR BOREL GRAPHS

Published online by Cambridge University Press:  01 May 2018

ADAM R. DAY  and
ANDREW S. MARKS
ADAM R. DAY
Affiliation:
SCHOOL OF MATHEMATICS, STATISTICS AND OPERATIONS RESEARCH VICTORIA UNIVERSITY OF WELLINGTON WELLINGTON, NEW ZEALANDE-mail:[email protected]
ANDREW S. MARKS
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF CALIFORNIA, LOS ANGELES LOS ANGELES, CA, USAE-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

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 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.

Keywords

03E1503D60descriptive set theoryeffective descriptive set theoryBorel graph combinatoricsBorel graph coloringFriedman-Stanley jumpgraph homomorphismFrechet ideals
Type
Articles
Information
The Journal of Symbolic Logic , Volume 83 , Issue 1 , March 2018 , pp. 13 - 28
Copyright
Copyright © The Association for Symbolic Logic 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Debs, G. and Raymond, J. S., Filter descriptive classes of Borel functions. Fundamenta Mathematicae, vol. 204 (2009), no. 3, pp. 189–213.Google Scholar
Friedman, H. and Stanley, L., A Borel reducibility theory for classes of countable structures, this Journal, vol. 54 (1989), no. 3, pp. 894–914.Google Scholar
Hell, P. and Nešetřil, J., Graphs and Homomorphisms, Series in Mathematics and its Applications, vol. 28, Oxford University Press, Oxford, 2004.Google Scholar
Kechris, A. S., Classical Descriptive Set Theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995.Google Scholar
Kechris, A. and Marks, A., Descriptive graph combinatorics, 2015. Preprint available at http://math.ucla.edu/∼marks.Google Scholar
Kechris, A. S., Solecki, S., and Todorcevic, S., Borel chromatic numbers. Advances in Mathematics, vol. 141 (1999), no. 1, pp. 1–44.CrossRefGoogle Scholar
Louveau, A., On the reducibility order between Borel equivalence relations, Logic, Methodology and Philosophy of Science, IX (Uppsala, 1991) (Prawtiz, D., Skyrms, B., and Westerståhl, D., editors), Studies in Logic and the Foundations of Mathematics, vol. 134, North-Holland, Amsterdam, 1994, pp. 151–155.Google Scholar
Marks, A., Slaman, T. A., and Steel, J. R., Martin’s conjecture, arithmetic equivalence, and countable borel equivalence relations, Ordinal Definability and Recursion Theory: The Cabal Seminar, Vol. III (Kechris, A. S., Löwe, B., and Steel, J. R., editors), Cambridge University Press, Cambridge, 2011, pp. 493–520.Google Scholar