Kerry Ojakian
Graduate Student
Department of Mathematical Sciences
Carnegie Mellon University
Title:
Ramsey theory in bounded arithmetic
Abstract:
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.