Short proofs of the Kneser-Lovász coloring principle
From MaRDI portal
Publication:1641004
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
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