Series: Penn State Logic Seminar

Date: Tuesday, November 6, 2001

Time: 2:30 - 3:45 PM

Place: 306 Boucke Building

Speaker: Tamara Lakins, Allegheny College, Mathematics

Title: 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.  We present
a survey of results and open questions concerning the complexity of
infinite homogeneous sets for effectively given (computable or
computably enumerable) colorings.