Inscriere cercetatori

Site nou !

Daca nu va puteti recupera parola (sau aveti alte probleme), scrieti-ne la pagina de contact. Situl vechi se gaseste la adresa old.ad-astra.ro

Short Proofs of the Kneser-Lovász Coloring Principle

Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în volumul unei conferinţe

Autori: James Aisenberg, Maria Luisa Bonet, Sam Buss, Adrian Craciun and Gabriel Istrate

Editorial: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), Lecture Notes in Computer Science vol. 9135, p.44-55, Springer Verlag, 2015.

Rezumat:

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.

Cuvinte cheie: Frege proofs, Kneser-Lovasz Theorem

URL: http://link.springer.com/chapter/10.1007/978-3-662-47666-6_4