University of Connecticut

Events Calendar

Connecticut Logic Seminar
Ramsey-Like Theorems and Moduli of Computation
Ludovic Patey (CNRS, Institut Camille Jordan, Lyon)

Monday, November 11, 2019
4:45pm – 6:00pm

Storrs Campus
MONT 214

Ramsey's Theorem Asserts That Every $$k$$-Coloring of $$[\omega]^n$$ Admits an Infinite Monochromatic Set. On the other hand, for every computable $$k$$-coloring of $$[\omega]^2$$ and every non-computable set $$C$$, there is an infinite monochromatic set $$H$$ such that $$C \not \leq_T H$$. The latter property is known as \textit{cone avoidance}.

In this talk, we introduce a natural class of Ramsey-like theorems encompassing many problems studied in reverse mathematics. We show that this class admits a maximal statement satisfying cone avoidance and use it as criterion to re-obtain many existing proofs of cone avoidance. This maximal statement asserts the existence, for every $$k$$-coloring of $$[\omega]^n$$, an infinite subdomain $$H \subseteq \omega$$ over which the coloring depends only on the sparsity of its elements. This confirms the intuition that Ramsey-like theorems compute Turing degrees only through the sparsity of its solutions.


Reed Solomon,

Connecticut Logic Seminar (primary)

Control Panel