10 citations · 18 across the 7 of their papers we have counts for
7 papers · 1 filter
The weakness of the Erdős-Moser theorem under arithmetic reductions
Ludovic Levy Patey, Ahmed Mimouni
The Erdős-Moser theorem says that every infinite tournament admits an infinite transitive subtournament. We study the computational behavior of the Erdős-Moser theo…
Partial orders and immunity in reverse mathematics
Ludovic Patey
We identify computability-theoretic properties enabling us to separate various statements about partial orders in reverse mathematics. We obtain simpler proofs of existing separati…
Somewhere over the rainbow Ramsey theorem for pairs
Ludovic Patey
The rainbow Ramsey theorem states that every coloring of tuples where each color is used a bounded number of times has an infinite subdomain on which no color appears twice. The re…
Iterative forcing and hyperimmunity in reverse mathematics
Ludovic Patey
The separation between two theorems in reverse mathematics is usually done by constructing a Turing ideal satisfying a theorem P and avoiding the solutions to a fixed instance of a…
Ramsey-type graph coloring and diagonal non-computability
Ludovic Patey
A function is diagonally non-computable (d.n.c.) if it diagonalizes against the universal partial computable function. D.n.c. functions play a central role in algorithmic randomnes…
Degrees bounding principles and universal instances in reverse mathematics
Ludovic Patey
A Turing degree d bounds a principle P of reverse mathematics if every computable instance of P has a d-computable solution. P admits a universal instance if there exists a computa…