2015 | OriginalPaper | Buchkapitel
Short Proofs of the Kneser-Lovász Coloring Principle
verfasst von : James Aisenberg, Maria Luisa Bonet, Sam Buss, Adrian Crãciun, Gabriel Istrate
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We prove that the propositional translations of the Kneser-Lovász theorem have polynomial size extended Frege proofs and quasi-polynomial size Frege proofs. We present a new counting-based combinatorial proof of the Kneser-Lovász theorem that avoids the topological arguments of prior proofs for all but finitely many cases for each
k
. We introduce a miniaturization of the octahedral Tucker lemma, called the
truncated Tucker lemma
: it is open whether its propositional translations have (quasi-)polynomial size Frege or extended Frege proofs.