Series: Penn State Logic Seminar

Date: Tuesday, October 28, 2003

Time: 2:30 - 3:45 PM

Place: 324 Sackett Building (note unusual location)

Speaker: Kerry Ojakian, Carnegie Mellon University, Mathematics

Title: 

The Probabilistic Method and Ramsey Theory in Bounded Arithmetic

Abstract:

Working in bounded arithmetic (Buss's S_2), we formalize various
applications of the probabilistic method.  The direct counting
argument does not work, but as long as the appropriate function can be
defined, we can use the weak pigeonhole principle.  Some of these
applications are to Ramsey Theory.