A complexity problem for Borel graphs - Sorbonne Université
Journal Articles Inventiones Mathematicae Year : 2021

A complexity problem for Borel graphs

Abstract

We show that there is no simple (e.g. finite or countable) basis for Borel graphs with infinite Borel chromatic number. In fact, it is proved that the closed subgraphs of the shift graph on [N]N with finite (or, equivalently, ≤3) Borel chromatic number form a ΣΣ12-complete set. This answers a question of Kechris and Marks and strengthens several earlier results.
Fichier principal
Vignette du fichier
Todorčević-Vidnyánszky2021_Article_AComplexityProblemForBorelGrap.pdf (418.23 Ko) Télécharger le fichier
Origin Publication funded by an institution

Dates and versions

hal-03235782 , version 1 (26-05-2021)

Identifiers

Cite

Stevo Todorčević, Zoltán Vidnyánszky. A complexity problem for Borel graphs. Inventiones Mathematicae, 2021, 226, pp.225 - 249. ⟨10.1007/s00222-021-01047-z⟩. ⟨hal-03235782⟩
39 View
146 Download

Altmetric

Share

More