Minimal definable graphs of definable chromatic number at least three

DOI10.1017/FMS.2020.58MaRDI QIDQ5149654zbMATH OpenOpenAlexFDO

Authors Raphaël Carroy, Benjamin D. Miller, David Schrittesser, Zoltán Vidnyánszky

Publication date 12 February 2021

Published in Forum of Mathematics, Sigma (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1906.08373

zbMATH Keywords

Borel bipartiteBorel coloring

Mathematics Subject Classification ID

Descriptive set theory (03E15) Coloring of graphs and hypergraphs (05C15) Classes of sets (Borel fields, (sigma)-rings, etc.), measurable sets, Suslin sets, analytic sets (28A05)

Abstract: We show that there is a Borel graph on a standard Borel space of Borel chromatic number three that admits a Borel homomorphism to every analytic graph on a standard Borel space of Borel chromatic number at least three. Moreover, we characterize the Borel graphs on standard Borel spaces of vertex-degree at most two with this property, and show that the analogous result for digraphs fails.

Recommendations

• Borel chromatic numbers
• Basis problems for Borel graphs
• A bound on measurable chromatic numbers of locally finite Borel graphs
• An antibasis result for graphs of infinite Borel chromatic number
• Borel chromatic number of closed graphs

Cites work

• A complexity problem for Borel graphs
• A determinacy approach to Borel combinatorics
• A Glimm-Effros Dichotomy for Borel Equivalence Relations
• An antibasis result for graphs of infinite Borel chromatic number
• Baire-class colorings: the first three levels
• Borel chromatic numbers
• Borel circle squaring
• Counterexamples to Hedetniemi's conjecture
• Essential countability of treeable equivalence relations
• Finite versus infinite: an insufficient shift
• Graph isomorphism in quasipolynomial time (extended abstract)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• Invariant descriptive set theory
• Measurable chromatic and independence numbers for ergodic graphs and group actions
• Measurable versions of the Lovász local lemma and measurable graph colorings
• Minimal definable graphs of definable chromatic number at least three
• ON THE EXISTENCE OF LARGE ANTICHAINS FOR DEFINABLE QUASI-ORDERS
• The chromatic number of the product of two 4-chromatic graphs is 4
• The graph-theoretic approach to descriptive set theory
• The smooth ideal

Cited in

(12)

• A complexity problem for Borel graphs
• Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022
• scientific article; zbMATH DE number 1076145 (Why is no real title available?)
• Jump operations for Borel graphs
• Minimal definable graphs of definable chromatic number at least three
• Basis problems for Borel graphs
• A dichotomy characterizing analytic digraphs of uncountable Borel chromatic number in any dimension
• An antibasis result for graphs of infinite Borel chromatic number
• scientific article; zbMATH DE number 5064065 (Why is no real title available?)
• Continuous 2-colorings and topological dynamics
• Measurable graph combinatorics
• ^1_1 effectivization in Borel combinatorics

This page was built for publication: Minimal definable graphs of definable chromatic number at least three

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