Nilava Metya, Rutgers University

Abstract

The Knaser graph K(n,k) is the graph whose vertices are the n-subsets of {1,2,..,2n+k} and two vertices are connected if and only if they don't intersect. An example is the Petersen graph (https://en.wikipedia.org/wiki/Petersen_graph) which is K(2,1). Knaser, in 1955, conjectured that the chromatic number of K(n,k) is k+2. In fact, the chromatic number for the Petersen graph is 1+2=3. I'll try to prove this conjecture in the limited time. The technique will be to show that k+2 is both the upper and lower bound. This graph is indeed (k+2)-colourable, which proves the upper bound. We'll use a combinatorial version of the Borsuk-Ulam theorem to prove the lower bound.