Generalized Kneser coloring theorems with combinatorial proofs

• 成果类型: Article
• 署名作者: Ziegler, GM
• 署名单位: Technical University of Berlin
• 刊物名称: INVENTIONES MATHEMATICAE
• ISSN/ISSBN: 0020-9910
• DOI: 10.1007/s002220100188
• 发表日期: 2002
• 页码: 671-691
• 关键词: chromatic number

摘要

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