Colloquium: “Path, trees, and the computational strength of a packed Ramsey’s theorem”

Marshall University Math Colloquium
April 14, 2014

Dr. Stephen Flood
University of Connecticut – Waterbury

Abstract
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.