Penn Arts & Sciences Logo

Logic and Computation Seminar

Monday, April 8, 2013 - 3:30pm

Stephen Flood

Pennsylvania State University

Location

University of Pennsylvania

4C8

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.