Generalized Kneser coloring theorems with combinatorial proofs |
| |
Authors: | Günter M Ziegler |
| |
Institution: | (1) Department of Mathematics, MA 6-2, TU Berlin, D-10623 Berlin, Germany |
| |
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.
Oblatum 17-IV-2001 & 12-IX-2001?Published online: 19 November 2001
An erratum to this article is available at . |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|