Short proofs of the Kneser-Lovász coloring principle

DOI10.1016/j.ic.2018.02.010zbMath1443.03040OpenAlexW2790199059WikidataQ113872845 ScholiaQ113872845MaRDI QIDQ1641004

James Aisenberg, Maria Luisa Bonet, Gabriel I. Istrate, Samuel R. Buss, Adrian Crǎciun

Publication date: 14 June 2018

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2117/124274

zbMATH Keywords

chromatic numberproof complexityTucker lemmaextended FregeKneser-Lovász theorem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Complexity of proofs (03F20)

Related Items

Approximate counting and NP search problems ⋮ On the number of star‐shaped classes in optimal colorings of Kneser graphs ⋮ 2-D Tucker is PPA complete

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Propositional proofs and reductions between NP search problems
• The provably total NP search problems of weak second order bounded arithmetic
• Kneser's conjecture, chromatic number, and homotopy
• Non-trivial intersecting families
• A constructive proof of Tucker's combinatorial lemma
• Propositional consistency proofs
• On the complexity of the parity argument and other inefficient proofs of existence
• Generalized Kneser coloring theorems with combinatorial proofs
• A combinatorical proof of Kneser's conjecture
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• Quasipolynomial size proofs of the propositional pigeonhole principle
• Proof Complexity and the Kneser-Lovász Theorem
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Short Proofs of the Kneser-Lovász Coloring Principle
• Polynomial size proofs of the propositional pigeonhole principle
• The relative efficiency of propositional proof systems
• Short Proofs for the Determinant Identities
• Improved witnessing and local improvement principles for second-order bounded arithmetic
• The Complexity of Propositional Proofs
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS

This page was built for publication: Short proofs of the Kneser-Lovász coloring principle