Generalized Kneser coloring theorems with combinatorial proofs
By Günter M. Ziegler. 2001
107 citations recorded by the source corpus.
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.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Mathematical Physics
View Paper: https://www.semanticscholar.org/paper/5c825ef810328ccfd4e6544908528500ec33d873
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
In Mathematical Physics
Citations in the corpus
- On the chromatic number of Kneser hypergraphs (2002, result): “This result was further extended by Ziegler [ 15 ], who proved a common generalization of Theorem 1.1 and of theorems of Alon et al. [1] and of Sarkaria [14].”