80-317 Introduction to Ramsey Theory

6 units, Carnegie Mellon University

While working on the decision problem for first order logic, Frank Ramsey [1930 developed a combinatorial approach that now bears his name. For one example of his idea, imagine that we construct an undirected graph on Kmany nodes, connecting each pair of nodes with edges of one of two colors, red or blue. How many nodes K3,2 does it take to insure that, no matter how we color the graph, there will be a trio of points each connected by the same color How large do we need to make K to guarantee a homogeneous subgraph of 3 nodes in 2 colors K 5 will not do, as this picture reveals. See image here httpsgoo.gltxagIS A 2coloring of 5 nodes with no homogeneous subgraph of 3 nodes. In this introduction we will consider some of the fundamental theorems of Ramsey Theory and a family of applications to logic, graph theory, number theory, and ergodic theory.

Prerequisites: none listed

Courseweave needs JavaScript to show sections, workloads and planning tools.