How do you prove Kneser's conjecture?

Answer 1

Kneser's conjecture: the minimum number of colors in order to color the K(n,k) is n-2k+2. Where K(n,k) is the graph on "n choose k" vertices were two vertices are connected iff they are disjoint.

Proof: assume by way of contradiction that there is a coloring in n-2k+1 colors. Define d=n-2k+1 and consider the d-dimensional sphere. Place n points numbered from 1..n on the sphere such that no d+1 points are on the same "equator".

Next, define open sets C_1,...,C_d as follows: C_i = {x: the half sphere were x is the center contains k points and the coresponding vertix in G is colored i}. Define F = S^d \ Union(C_i).

By Bursuk-Ulam for every cover of the n-dimensional ball (using l1 norm) using n+1

open/closed sets there is a point x for which x,-x are in the same set.

We get that there is a set with x,-x in it:

- If it's F, we reach a contradiction because there are more that d+1 vertices on the equator between x and -x.

- If it's one of the C_i-s we reach a contradiction: because the points that x "sees" are disjoint from the ones -x "sees". So in K(n,k) there is an edge between them - thus the coloring is not valid.

QED