2026-04-18T03:31:41Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/1242742026-01-24T03:31:20Zcom_2072_1033col_2072_452950

Short proofs of the Kneser-Lovász coloring principle Aisenberg, James Bonet Carbonell, M. Luisa Buss, Sam Craciun, Adrian Istrate, Gabriel Universitat Politècnica de Catalunya. Departament de Ciències de la Computació Universitat Politècnica de Catalunya. LOGPROG - Lògica i Programació Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica Polynomials Combinatorial proof Frege proofs Polynomial size Quasi-poly-nomial Kneser–Lovász theorem Hilton–Milner theorem Polinomis We prove that propositional translations of the Kneser–Lovász theorem have polynomial size extended Frege proofs and quasi-polynomial size Frege proofs for all fixed values of k. We present a new counting-based combinatorial proof of the K neser–Lovász theorem based on the Hilton–Milner theorem; this avoids the topological arguments of prior proofs for all but finitely many base cases. We introduce new “truncated Tucker lemma” principles, which are miniaturizations of the octahedral Tucker lemma. The truncated Tucker lemma implies the Kneser–Lovász theorem. We show that the k=1 case of the truncated Tucker lemma has polynomial size extended Frege proofs. Peer Reviewed Postprint (author's final draft) 2018-08 Article Aisenberg, J., Bonet, M., Buss, S., Craciun, A., Istrate, G. Short proofs of the Kneser-Lovász coloring principle. "Information and computation", Agost 2018, vol. 261, Part 2, p. 296-310. 0890-5401 https://hdl.handle.net/2117/124274 10.1016/j.ic.2018.02.010 eng https://www.sciencedirect.com/science/article/pii/S0890540118300130 info:eu-repo/grantAgreement/MINECO//TIN2013-48031-C4-1-P/ES/TASSAT 2: TEORIA Y APLICACIONES EN SATISFACTIBILIDAD Y OPTIMIZACION DE RESTRICCIONES/ http://creativecommons.org/licenses/by-nc-nd/3.0/es/ Open Access Attribution-NonCommercial-NoDerivs 3.0 Spain 15 p. application/pdf