Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Theses and dissertations
Ad Astra association
Press releases
Funding opportunities
>> Românã

James Aisenberg, Maria Luisa Bonet, Sam Buss, Adrian Craciun and Gabriel Istrate. Short Proofs of the Kneser-Lovász Coloring Principle. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015) , Lecture Notes in Computer Science vol. 9135, pp. 44-55. 2015.

Abstract: We prove that the propositional translations of the Kneser-Lovasz theorem have polynomial size extended Frege proofs and quasi-polynomial size Frege proofs. We present a new counting-based combinatorial proof of the Kneser-Lovasz theorem that avoids the topological arguments of prior proofs. We introduce a miniaturization of the octahedral Tucker lemma, called the truncated Tucker lemma. The propositional translations of the truncated Tucker lemma are polynomial size and they imply the Kneser-Lovasz principles with polynomial size Frege proofs. It is open whether they have (quasi-)polynomial size Frege or extended Frege proofs.

Keywords: Frege proofs, Kneser-Lovasz Theorem


Posted by Gabriel Istrate


© Ad Astra 2001-2013