Kurt Gödel Research Center

2013 seminar talk: Weak pigeonhole principles

Talk held by Moritz Müller (KGRC) at the KGRC seminar on 2013-03-14.

Abstract

The pigeonhole principle states that, if $n+1$ pigeons fly into $n$ holes then some hole must be doubly occupied. Weak pigeonhole principles state the same but for $2n$ or $n^2$ many pigeons. The talk surveys results and open problems concerning the proof complexity of these principles. Then some new results concerning a relativized such principle are presented. This principle states that if at least $2n$ out of $n^2$ many pigeons fly into $n$ holes, then some hole must be doubly occupied. This is joint work with Albert Atserias and Sergi Oliva.