Complexity of codes for Ramsey positive sets

2024/05/14 by Allison Wang, Wang, Allison
Computer Science · Mathematics · #03E15 #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #FOS: Mathematics #Limits and Structures in Graph Theory #Logic (math.LO)

paper · pdf · doi:10.48550/arxiv.2405.08575

openalex publication_date 2024/05/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Sabok showed that the set of codes for G_δ Ramsey positive subsets of [ω]^ω is \mathbfΣ¹₂-complete. We extend this result by providing sufficient conditions for the set of codes for G_δ Ramsey positive subsets of an arbitrary topological Ramsey space to be \mathbfΣ¹₂-complete.

Related

• Complexity of Ramsey null sets
• Set-coloring Ramsey numbers and error-correcting codes near the zero-rate threshold
• Combinatorial Bounds for Codes over Metric Spaces: Ramsey-Sidorenko Thresholds and Subgraph Counts
• Odd-Ramsey numbers of complete bipartite graphs
• Set-coloring Ramsey numbers via codes