Logic Seminar

Jun Le GohCornell University
How hard is it to compute homogeneous sets for colorings?

Wednesday, November 9, 2016 - 4:00pm
Malott 206

Ramsey's theorem states that for every coloring of n-tuples, there is an infinite set H which is homogeneous, i.e., all of the n-tuples in H have the same color. In 1972, Jockusch showed that as the size of tuples increases, it becomes harder to compute infinite homogeneous sets. What if we fix the size of tuples but increase the number of colors? Would that make it harder to compute infinite homogeneous sets? We present results of Patey which say yes, and more. Knowledge of reducibilities will not be assumed.