Minimal definable graphs of definable chromatic number at least three

DOI10.1017/fms.2020.58zbMath1498.03103arXiv1906.08373OpenAlexW3127619189MaRDI QIDQ5149654

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

Publication date: 12 February 2021

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

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

zbMATH Keywords

Borel coloringBorel bipartite

Mathematics Subject Classification ID

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

Related Items (5)

Continuous 2-colorings and topological dynamics ⋮ Measurable graph combinatorics ⋮ Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022 ⋮ Minimal definable graphs of definable chromatic number at least three ⋮ A complexity problem for Borel graphs

Cites Work

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

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