Springe direkt zu Inhalt

Generalized Kneser coloring theorems with combinatorial proofs

Günter M. Ziegler – 2002

The Kneser conjecture (1955) was proved by Lov\'asz (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\v{s}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\'asz, Sarkaria, and Kriz. We also give a combinatorial proof of Schrijver's theorem.

Titel
Generalized Kneser coloring theorems with combinatorial proofs
Verfasser
Günter M. Ziegler
Datum
2002
Erschienen in
Inventiones math., volume 147, pages 671-691
Art
Text