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.
Mathematical Logic at Penn State
Department of Mathematics