The weakness of the Erdős-Moser theorem under arithmetic reductions

2023/10/27 by Ludovic Patey, Patey, Ludovic Levy, Ahmed Mimouni +1
Computer Science · #03B30 #Advanced Graph Theory Research #Artificial Intelligence in Games #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO)

paper · pdf · doi:10.48550/arxiv.2310.17968

openalex publication_date 2023/10/27 · openalex created_date 2023/11/01 · openalex updated_date 2026/07/28

Abstract

The Erdős-Moser theorem (EM) says that every infinite tournament admits an infinite transitive subtournament. We study the computational behavior of the Erdős-Moser theorem with respect to the arithmetic hierarchy, and prove that Δ⁰_n instances of EM admit low_n+1 solutions for every n ≥ 1, and that if a set B is not arithmetical, then every instance of EM admits a solution relative to which B is still not arithmetical. We also provide a level-wise refinement of this theorem. These results are part of a larger program of computational study of combinatorial theorems in Reverse Mathematics.

Related

• Dominating the Erdos-Moser theorem in reverse mathematics
• The Erdős--Moser sum-free set problem via improved bounds for k-configurations
• Short proofs in combinatorics, probability and number theory II
• The reverse mathematics of the Thin set and Erdős-Moser theorems
• 1-color-avoiding paths, special tournaments, and incidence geometry