Preprint:
James Aisenberg, Maria Luisa Bonet, Sam Buss
"Quasipolynomial Size Frege Proofs of Frankl's
Theorem on the Trace of Sets"
Journal of Symbolic Logic, 81, 2 (2016) 1-24.
Download manuscript: PDF.
Abstract: We extend results of Bonet, Buss and Pitassi on Bondy's Theorem and of Nozaki, Arai and Arai on Boolob\'as' Theorem by proving that Frankl's Theorem on the trace of sets has quasipolynomial size Frege proofs. For constant values of the parameter~$t$, we prove that Frankl's Theorem has polynomial size $\AC^0$-Frege proofs from instances of the pigeonhole principle.