Ernest Schimmerling

Mathematical logic seminar - January 22, 2003

Speaker: Kerry Ojakian
Graduate Student
Department of Mathematical Sciences
Carnegie Mellon University

Title: Ramsey theory in bounded arithmetic

Working in bounded arithmetic, Pudlak proved various cases of Ramsey's Theorem. His proof in fact shows that the weak pigeonhole principle (WPHP) implies the Ramsey theorem. I will discuss some recent work of mine on proving a "reversal" in bounded arithmetic, that is, a certain form of the Ramsey theorem in fact implies the WPHP. This involves providing a constructive lower bound for a Ramsey number. I will also discuss some work on finding non-constructive lower bounds by formalizing the probabilistic method within bounded arithmetic.