2013 seminar talk: Weak pigeonhole principles

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


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.

Bottom menu

Kurt Gödel Research Center for Mathematical Logic. Währinger Straße 25, 1090 Wien, Austria. Phone +43-1-4277-50501. Last updated: 2010-12-16, 04:37.