Inscriere cercetatori

Asociatia Ad Astra a cercetatorilor romani lanseaza BAZA DE DATE A CERCETATORILOR ROMANI DIN DIASPORA. Scopul acestei baze de date este aceea de a stimula colaborarea dintre cercetatorii romani de peste hotare dar si cu cercetatorii din Romania. Cercetatorii care doresc sa fie nominalizati in aceasta baza de date sunt rugati sa trimita un email la cristian.presura@gmail.com

Short Proofs of the Kneser-Lovász Coloring Principle

Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în revistã ştiinţificã

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

Editorial: Information and Computation, 261 part 2, p.296-310, 2018.

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.

A preliminary (conference) version of this paper has appeared in Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), Lecture Notes in Computer Science vol. 9135, 44-55, Springer Verlag, 2015, http://link.springer.com/chapter/10.1007/978-3-662-47666-6_4

Cuvinte cheie: Frege proofs, Kneser-Lovasz Theorem

URL: https://www.sciencedirect.com/science/article/pii/S0890540118300130