Professor Tamara Lakins, Allegheny College

Ramsey's theorem and computability theory

An infinite version of Ramsey's theorem states that for every coloring of
$[\omega]^n$ (the set of all $n$--element subsets of $\omega$) by finitely
many colors, there is an infinite set $A$ which is homogeneous for that
coloring, i.e., all elements of $[A]^n$ have the same color. After an
introduction to the necessary background in computability theory, we
present a survey of results concerning the complexity of infinite
homogeneous sets for effectively given (computable or computably
enumerable) colorings.