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.
Weak pigeonhole principles
14.03.2013 15:00 - 16:30
Organiser:
KGRC
Location:
SR 101, 2. St., Währinger Str. 25