Ramsey's theorem states that each coloring has an infinite homo- geneous 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 introduce a related combinatorial principle called 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.
Logic and Computation Seminar
Monday, April 8, 2013 - 3:30pm
Stephen Flood
Pennsylvania State University