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!