A complexity problem for Borel graphs

DOI10.1007/S00222-021-01047-ZMaRDI QIDQ2238048zbMATH OpenOpenAlexFDO

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

Publication date 29 October 2021

Published in Inventiones Mathematicae (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

\(\Sigma^1_2\)-completeantibasisBorel chromatic numberBorel graphchromatic numberHedetniemi's conjecture

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)

Recommendations

• Basis problems for Borel graphs
• An antibasis result for graphs of infinite Borel chromatic number
• Borel chromatic numbers
• Basis theorems for non-potentially closed sets and graphs of uncountable Borel chromatic number
• Borel chromatic number of closed graphs

Cites work

• A determinacy approach to Borel combinatorics
• An antibasis result for graphs of infinite Borel chromatic number
• Basis problems for Borel graphs
• Borel chromatic numbers
• Complexity of Ramsey null sets
• Counterexamples to Hedetniemi's conjecture
• Descriptive set theory
• Finite versus infinite: an insufficient shift
• Hedetniemi's conjecture---a survey
• scientific article; zbMATH DE number 4068856 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 1420843 (Why is no real title available?)
• Hyperarithmetically Encodable Sets
• Linear algebraic groups and countable Borel equivalence relations
• Measurable chromatic and independence numbers for ergodic graphs and group actions
• Minimal definable graphs of definable chromatic number at least three
• Recursion theory. Computational aspects of definability
• Subsystems of second order arithmetic
• 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
• The graph-theoretic approach to descriptive set theory
• The Set of Better Quasi Orderings is ∏
• Towards better: a motivated introduction to better-quasi-orders

Cited in

(21)

• A bound for the complexity of a simple graph
• Borel colouring bad rays
• Canonical forms of shift-invariant maps on \([\mathbb N]^{\infty}\)
• Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022
• On the complexity of computing the excessive \([B]\)-index of a graph
• Graph painting and the Borel-de Siebenthal property
• scientific article; zbMATH DE number 3874608 (Why is no real title available?)
• Orienting Borel graphs
• Haar-\(\mathcal{I}\) sets: looking at small sets in Polish groups through compact glasses
• Minimal definable graphs of definable chromatic number at least three
• Borel chromatic numbers of graphs of commuting functions
• Continuous 2-colorings and topological dynamics
• Tall 𝐹_{𝜎} subideals of tall analytic ideals
• Measurable graph combinatorics
• Borel fractional colorings of Schreier graphs
• A complexity problem for Borel graphs
• Complexity of finite Borel asymptotic dimension
• ^1_1 effectivization in Borel combinatorics
• Complexity of codes for Ramsey positive sets
• Continuous colorings on compact spaces
• Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree

This page was built for publication: A complexity problem for Borel graphs

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