کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6873785 | 1440705 | 2018 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Short proofs of the Kneser-Lovász coloring principle
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
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 Kneser-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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 261, Part 2, August 2018, Pages 296-310
Journal: Information and Computation - Volume 261, Part 2, August 2018, Pages 296-310
نویسندگان
James Aisenberg, Maria Luisa Bonet, Sam Buss, Adrian CrÄciun, Gabriel Istrate,