Marshall University Math Colloquium

April 14, 2014

“Path, trees, and the computational strength of a packed Ramsey's theorem”

Dr. Stephen Flood

University of Connecticut – Waterbury


Ramsey theory is a branch of combinatorics which provides results like the following: any large enough graph must either contain a large complete subgraph (all vertices connected) or a large independent set (no vertices connected). In this talk, we will introduce a “packed" version of Ramsey's theorem, due to Erdos and Galvin, which combines aspects of finite and infinite Ramsey theory. We will discuss the techniques used to extract these packed homogeneous sets, and we will study their strength using the tools of computability theory and reverse mathematics.