= Solution
The <Kneser graph> $KG(n,k)$ has the $k$-element subsets of $[n]$ as its <vertices>; two <vertices> are adjacent exactly when the corresponding subsets are disjoint. The <Lovász theorem on Kneser graphs> determines its <chromatic number>. A <graph colouring> is therefore a partition of the $k$-sets into <intersecting families>.
First construct a <graph colouring> with $d+2=n-2k+2$ colours. If a $k$-set meets $[d+1]$, give it the colour of its least element. Give every remaining $k$-set colour $d+2$. Two sets with one of the first $d+1$ colours share that colour's element. The last colour consists of $k$-sets in a $(2k-1)$-element ground set, so it too is an <intersecting family>. Thus $\chi(KG(n,k))\leq d+2$.
For the converse we establish the <Gale hemisphere lemma> explicitly, using a signed <moment curve>. Choose $t_1<\cdots<t_n$ and put
$$
w_i=(-1)^i(1,t_i,\ldots,t_i^d),\qquad v_i=w_i/\|w_i\|\in S^d.
$$
Every <open hemisphere> $\{v:x\cdot v>0\}$ contains at least $k$ labelled points $v_i$. To see this, put $p(t)=x_0+x_1t+\cdots+x_dt^d$. It is a nonzero <polynomial> of <polynomial degree> at most $d$. First suppose none of the $p(t_i)$ vanishes. Write $b_i=\operatorname{sgn}((-1)^ip(t_i))$. If only $P\leq k-1$ of the $b_i$ were positive, the $N=n-P$ negative signs would occupy at most $P+1$ consecutive blocks. There would be at least
$$
N-(P+1)=n-2P-1\geq d+1
$$
adjacent pairs with both $b_i,b_{i+1}$ negative. Each such pair forces $p(t_i)$ and $p(t_{i+1})$ to have opposite signs. The <intermediate value theorem> would give $d+1$ distinct <roots of a polynomial>, a contradiction.
If $p$ vanishes at $z$ of the sample points, then $z\leq d$. A <Lagrange interpolation polynomial> $q$ of <polynomial degree> at most $z-1$ can be chosen with $(-1)^iq(t_i)<0$ at all those points. For sufficiently small $\varepsilon>0$, the <polynomial> $p+\varepsilon q$ keeps every previously nonzero sign, has no zero sample values, and makes every previously zero value negative after multiplication by $(-1)^i$. Its positive count is exactly the positive count of $p$, so the preceding argument proves the <open hemisphere> assertion also in this case. For $d=0$, the labelled points alternate between the two points of $S^0$; distinct labels, rather than distinct positions, are what is needed.
Suppose now that $KG(n,k)$ had a <graph colouring> with at most $d+1$ colours, padding the palette with unused colours if necessary. For each colour $j$, let
$$
U_j=\bigcup_{\substack{A\subseteq[n],\ |A|=k\\A\text{ has colour }j}}
\{x\in S^d:x\cdot v_i>0\text{ for every }i\in A\}.
$$
These are <open sets>, and the <Gale hemisphere lemma> says that they cover $S^d$. If both $x$ and $-x$ belonged to $U_j$, two $k$-sets of colour $j$ would lie in opposite <open hemispheres>. They would be disjoint, hence adjacent in the <Kneser graph>, contradicting the <graph colouring>. The <Lusternik-Schnirelmann-Borsuk theorem> excludes this cover. Therefore \b[the lower bound matches the explicit colouring]:
$$
\boxed{\chi(KG(n,k))=d+2=n-2k+2.}
$$
Back to article page
