Lovász theorem on Kneser graphs
ID: lovasz-theorem-on-kneser-graphs
For integers , the chromatic number of the Kneser graph is . The upper bound colours by the least element among the first elements, with one final colour for all other sets. The Gale hemisphere lemma and the Lusternik-Schnirelmann-Borsuk theorem give the matching lower bound.
New to topics? Read the docs here!