Full name: Ahmed Mimouni
Affiliation: Paris-East Créteil University, LACL laboratory

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

Absract: The Erdos-Moser theorem (EM) says that every infinite tournament admits an infinite transitive subtournament. We study the computational behavior of the Erdos-Moser theorem with respect to the arithmetic hierarchy, and prove that \Delta^0_n instances of EM admit low_{n+1} solutions for every n \geq 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.