A complexity problem for Borel graphs

• 成果类型: Article
• 署名作者: Todorcevic, Stevo; Vidnyanszky, Zoltan
• 署名单位: Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Sorbonne Universite; Universite Paris Cite; University of Toronto; California Institute of Technology
• 刊物名称: INVENTIONES MATHEMATICAE
• ISSN/ISSBN: 0020-9910
• DOI: 10.1007/s00222-021-01047-z
• 发表日期: 2021
• 页码: 225-249
• 关键词: chromatic number; infinite; product; set

摘要

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 Sigma(1)(2)-complete set. This answers a question of Kechris and Marks and strengthens several earlier results.