Ramsey, expanders, and Borel chromatic numbers

2022/05/04 by Jan Grebík, Grebík, Jan, Zoltán Vidnyánszky +1
Computer Science · Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Limits and Structures in Graph Theory #Logic (math.LO) #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2205.01839

openalex publication_date 2022/05/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We construct bounded degree acyclic Borel graphs with large Borel chromatic number using a graph arising from Ramsey theory and limits of expander sequences.

Related

• Descriptive Chromatic Numbers of Locally Finite and Everywhere Two Ended Graphs
• A complexity problem for Borel graphs
• Borel chromatic number of closed graphs
• Borel chromatic numbers of closed graphs and forcing with uniform trees
• Separating Tree-chromatic number from Path-chromatic Number