A complexity problem for Borel graphs

DOI10.1007/s00222-021-01047-zOpenAlexW3161154317MaRDI QIDQ2238048

Zoltán Vidnyánszky, Stevo Todorčević

Publication date: 29 October 2021

Published in: Inventiones Mathematicae (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numberHedetniemi's conjectureBorel graphBorel chromatic number\(\Sigma^1_2\)-completeantibasis

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

Continuous 2-colorings and topological dynamics ⋮ Tall 𝐹_{𝜎} subideals of tall analytic ideals ⋮ 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 ⋮ Orienting Borel graphs ⋮ Haar-$\mathcal I$ sets: looking at small sets in Polish groups through compact glasses

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of Ramsey null sets
• The chromatic number of the product of two 4-chromatic graphs is 4
• The chromatic number of the product of two \(\aleph _ 1\)-chromatic graphs can be countable
• Borel chromatic numbers
• Measurable chromatic and independence numbers for ergodic graphs and group actions
• Recursion theory. Computational aspects of definability
• Counterexamples to Hedetniemi's conjecture
• Finite versus infinite: an insufficient shift
• Towards better: a motivated introduction to better-quasi-orders
• A determinacy approach to Borel combinatorics
• Hyperarithmetically Encodable Sets
• Linear algebraic groups and countable Borel equivalence relations
• The Set of Better Quasi Orderings is ∏
• The graph-theoretic approach to descriptive set theory
• Minimal definable graphs of definable chromatic number at least three
• An antibasis result for graphs of infinite Borel chromatic number
• Hedetniemi's conjecture---a survey