Generalized Kneser coloring theorems with combinatorial proofs
arXiv:math/0103146 · doi:10.1007/s002220100188
Abstract
The Kneser conjecture (1955) was proved by Lovász (1978) using the Borsuk-Ulam theorem; all subsequent proofs, extensions and generalizations also relied on Algebraic Topology results, namely the Borsuk-Ulam theorem and its extensions. Only in 2000, Matoušek provided the first combinatorial proof of the Kneser conjecture. Here we provide a hypergraph coloring theorem, with a combinatorial proof, which has as special cases the Kneser conjecture as well as its extensions and generalization by (hyper)graph coloring theorems of Dol'nikov, Alon-Frankl-Lovász, Sarkaria, and Kriz. We also give a combinatorial proof of Schrijver's theorem.
19 pages, 4 figures
Cited by in corpus (6)
- On Chromatic Number of Kneser Hypergraphs
- Combinatorial Stokes formulas via minimal resolutions
- Sparse Kneser graphs are Hamiltonian
- On the Chromatic Thresholds of Hypergraphs
- A new lower bound for the chromatic number of general Kneser hypergraphs
- New construction of graphs with high chromatic number and small clique