Logic Seminar

Steven FloodUniversity of Connecticut, Storrs
Paths, trees, and the computational strength of some Ramsey-type theorems

Tuesday, March 18, 2014 - 2:55pm
Malott 206

Ramsey's theorem states that each coloring has an infinite homogeneous set, but these sets can be arbitrarily spread out. Paul Erdos and Fred Galvin proved that for each coloring $f$, there is an infinite set that is "packed together" which is given "a small number" of colors by $f$. In this talk, we will give the precise statement of this packed Ramsey's theorem, and discuss its computational and reverse mathematical strength. We will also discuss a related combinatorial principle called $\mathsf{RKL}$ which combines features of Weak Konig's Lemma and Ramsey's Theorem. We will give a precise statement of this principle and two of its generalizations, and discuss their reverse mathematical strength.