Generalized Kneser coloring theorems with combinatorial proofs
Generalized Kneser coloring theorems with combinatorial proofs
复制标题
具有组合证明的广义 Kneser 着色定理
DOI：
10.1007/s002220100188
复制
发表时间：
2001
影响因子：
3.1
通讯作者：
G. Ziegler
中科院分区：
文献类型：
--
作者：
G. Ziegler
Kneser猜想（1955）由Lovász（1978）使用Borsuk-Ulam定理证明;所有随后的证明、扩展和推广也依赖于代数拓扑学的结果，即Borsuk-Ulam定理及其扩展。直到2000年，Matoušek才首次给出了Kneser猜想的组合证明。在这里，我们提供了一个超图着色定理，并给出了组合证明，该定理的特殊情况是Kneser猜想及其由Dol'nikov、Alon-Frankl-Lovász、Sarkaria和Kriz的（超图）着色定理进行的扩展和推广。我们还给出了Schrijver定理的一个组合证明。
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.