[proofplan] We prove matching upper and lower bounds for the chromatic number. The upper bound is an explicit colouring by least elements, with one final colour for all $k$-subsets contained in a tail of size $2k-1$. For the lower bound, set $d:=n-2k$, use [Gale's lemma](/theorems/6487) to place the labelled ground set on the sphere $S^d$, and convert any colouring with at most $d+1$ colours into an open cover of $S^d$ by $d+1$ sets. Properness of the colouring prevents every colour-detection set from containing an antipodal pair, contradicting the Lyusternik-Schnirelmann antipodal cover theorem. [/proofplan] [step:Construct a proper colouring with $n-2k+2$ colours] Let $[n]$ denote the finite set $\{1,\dots,n\}$. Let $V$ denote the vertex set of $KG(n,k)$, so \begin{align*} V:=\{A\subset [n]: |A|=k\}. \end{align*} Two vertices $A,B\in V$ are adjacent exactly when $A\cap B=\varnothing$. Define the integer \begin{align*} d:=n-2k. \end{align*} Since $n\geq 2k$, we have $d\geq 0$, and the desired number of colours is $d+2$. Define the colouring map $\kappa:V\to \{1,\dots,d+2\}$ as follows. For $A\in V$, set $\kappa(A):=\min A$ if $\min A\leq d+1$, and set $\kappa(A):=d+2$ if $\min A\geq d+2$. We verify that $\kappa$ is proper. If $\kappa(A)=\kappa(B)=i$ for some $i\in\{1,\dots,d+1\}$, then $\min A=\min B=i$, so $i\in A\cap B$. Hence $A$ and $B$ are not adjacent. If $\kappa(A)=\kappa(B)=d+2$, then \begin{align*} A,B\subset \{d+2,d+3,\dots,n\}. \end{align*} The set $\{d+2,d+3,\dots,n\}$ has cardinality \begin{align*} n-(d+2)+1=n-d-1=2k-1. \end{align*} If $A$ and $B$ were disjoint, then $A\cup B$ would have cardinality $2k$ and would be contained in a set of cardinality $2k-1$, which is impossible. Thus $A\cap B\neq\varnothing$, so $A$ and $B$ are not adjacent. Every colour class of $\kappa$ is therefore an independent set. Hence \begin{align*} \chi(KG(n,k))\leq d+2=n-2k+2. \end{align*} [guided] We want an explicit colouring using $n-2k+2$ colours. It is useful to abbreviate this number by defining \begin{align*} d:=n-2k. \end{align*} Because $n\geq 2k$, this is a nonnegative integer, and the target number of colours is $d+2$. The vertices of the Kneser graph are the $k$-element subsets of $[n]=\{1,…,n\}$: \begin{align*} V:=\{A\subset [n]: |A|=k\}. \end{align*} Two vertices are adjacent precisely when they are disjoint. Therefore a colouring is proper exactly when any two vertices with the same colour intersect. Define $\kappa:V\to\{1,…,d+2\}$ by looking at the least element of a vertex. If $\min A\leq d+1$, give $A$ colour $\min A$. If $\min A\geq d+2$, give $A$ the final colour $d+2$. For the first $d+1$ colours, the verification is direct. If two vertices $A$ and $B$ both have colour $i$ with $1\leq i\leq d+1$, then both have least element $i$. In particular, $i\in A\cap B$, so $A$ and $B$ are not disjoint and hence not adjacent. For the final colour, every vertex of that colour lies in the tail \begin{align*} T:=\{d+2,d+3,\dots,n\}. \end{align*} The size of this tail is \begin{align*} |T|=n-(d+2)+1=n-d-1=2k-1. \end{align*} If two $k$-element subsets $A,B\subset T$ were disjoint, then their union would have $2k$ elements. This cannot happen inside a set with only $2k-1$ elements. Therefore any two vertices of the final colour intersect. All colour classes are independent sets, so $\kappa$ is a proper colouring with $d+2$ colours. Thus \begin{align*} \chi(KG(n,k))\leq d+2=n-2k+2. \end{align*} [/guided] [/step] [step:Place the labelled ground set on a sphere using Gale's lemma] Let $S^d$ denote the unit sphere in $\mathbb{R}^{d+1}$ with its [subspace topology](/page/Subspace%20Topology) and Euclidean dot product $\cdot$. We use Gale's lemma in the following standard form: if $k\geq 1$, $n\geq 2k$, and $d=n-2k$, then there exist points $p_1,\dots,p_n\in S^d$, not necessarily distinct, such that every open hemisphere of $S^d$ contains at least $k$ of these labelled points. The hypotheses of Gale's lemma are exactly satisfied: the theorem assumes $k\geq 1$ and $n\geq 2k$, and we have defined $d=n-2k$. Choose points $p_1,\dots,p_n\in S^d$ with Gale's property. For $x\in S^d$, define the positive index set \begin{align*} P(x):=\{i\in [n]: p_i\cdot x>0\} \end{align*} and the negative index set \begin{align*} N(x):=\{i\in [n]: p_i\cdot x<0\}. \end{align*} The open hemisphere centred at $x$ is $\{y\in S^d:y\cdot x>0\}$, so Gale's lemma gives \begin{align*} |P(x)|\geq k \end{align*} for every $x\in S^d$. Since $N(x)=P(-x)$, the same lemma applied to the centre $-x$ gives \begin{align*} |N(x)|\geq k. \end{align*} [guided] The lower bound will use topology, so we first replace the finite ground set $[n]$ by $n$ labelled points on a sphere. Let $S^d$ be the unit sphere in $\mathbb{R}^{d+1}$, equipped with its usual topology and Euclidean dot product $\cdot$. We invoke Gale's lemma in the exact form needed here: if $k\geq 1$, $n\geq 2k$, and $d=n-2k$, then there are labelled points $p_1,…,p_n\in S^d$, repetitions allowed, such that every open hemisphere of $S^d$ contains at least $k$ of the labelled points. The theorem's hypotheses give $k\geq 1$ and $n\geq 2k$, so Gale's lemma applies with our definition $d=n-2k$. Fix such points $p_1,…,p_n$. For each $x\in S^d$, define \begin{align*} P(x):=\{i\in[n]:p_i\cdot x>0\}. \end{align*} This is the set of labels whose points lie in the open hemisphere centred at $x$. Also define \begin{align*} N(x):=\{i\in[n]:p_i\cdot x<0\}. \end{align*} This is the corresponding set for the opposite open hemisphere, because $p_i\cdot(-x)>0$ is equivalent to $p_i\cdot x<0$. By Gale's lemma, the hemisphere centred at $x$ contains at least $k$ labelled points, so \begin{align*} |P(x)|\geq k. \end{align*} Applying the same statement to the centre $-x$ gives \begin{align*} |N(x)|=|P(-x)|\geq k. \end{align*} These two inequalities are the bridge between the topology of the sphere and the vertices of the Kneser graph: each hemisphere contains enough labels to choose a $k$-element vertex. [/guided] [/step] [step:Turn a colouring with too few colours into an antipodal open cover] Assume, toward a contradiction, that $KG(n,k)$ has a proper colouring using at most $d+1$ colours. Then there is a positive integer $r$ with $r\leq d+1$ and a proper colouring map \begin{align*} c:V\to\{1,\dots,r\}. \end{align*} For each colour $j\in\{1,\dots,r\}$, define \begin{align*} U_j:=\{x\in S^d:\text{there exists }A\subset P(x)\text{ with }|A|=k\text{ and }c(A)=j\}. \end{align*} Each $U_j$ is open in $S^d$. If $x\in U_j$, choose $A\subset P(x)$ with $|A|=k$ and $c(A)=j$. For every $i\in A$, the strict inequality $p_i\cdot x>0$ holds. Since the function $y\mapsto p_i\cdot y$ from $S^d$ to $\mathbb{R}$ is continuous for each fixed $i$, and since $A$ is finite, these strict inequalities hold simultaneously on some open neighbourhood of $x$ in $S^d$. The same set $A$ witnesses that every point of this neighbourhood lies in $U_j$. The sets $U_1,…,U_r$ cover $S^d$. Indeed, for any $x\in S^d$, the inequality $|P(x)|\geq k$ permits choosing a set $A\subset P(x)$ with $|A|=k$. Then $A\in V$, and $x\in U_{c(A)}$. [guided] Suppose the lower bound is false. Then there exists a proper colouring using only $r$ colours, where $r$ is a positive integer satisfying $r\leq d+1$. Denote this colouring by \begin{align*} c:V\to\{1,\dots,r\}. \end{align*} We convert this finite colouring into open subsets of the sphere. For each colour $j\in\{1,…,r\}$, define \begin{align*} U_j:=\{x\in S^d:\text{there exists }A\subset P(x)\text{ with }|A|=k\text{ and }c(A)=j\}. \end{align*} Thus $x\in U_j$ means that the positive hemisphere centred at $x$ contains a $k$-element vertex of colour $j$. We first prove openness. Fix $x\in U_j$. By definition, there is a particular $k$-element set $A\subset P(x)$ with $c(A)=j$. For every $i\in A$, we have \begin{align*} p_i\cdot x>0. \end{align*} For each fixed $i$, the map $S^d\to\mathbb{R}$ given by $y\mapsto p_i\cdot y$ is continuous because it is the restriction of a linear functional on $\mathbb{R}^{d+1}$. Since $A$ is finite, the finitely many inequalities $p_i\cdot y>0$ for $i\in A$ remain true on a common open neighbourhood of $x$ in $S^d$. On that neighbourhood, the same set $A$ is still contained in $P(y)$ and still has colour $j$. Therefore the neighbourhood is contained in $U_j$, proving that $U_j$ is open. Next we prove the cover property. Fix any $x\in S^d$. From Gale's lemma we have $|P(x)|\geq k$, so there exists a $k$-element subset $A\subset P(x)$. This set $A$ is a vertex of $KG(n,k)$, hence it has a colour $c(A)\in\{1,…,r\}$. By the definition of $U_{c(A)}$, the point $x$ belongs to $U_{c(A)}$. Since $x$ was arbitrary, the family $U_1,…,U_r$ covers $S^d$. [/guided] [/step] [step:Use properness to exclude antipodal pairs in every colour set] Fix $j\in\{1,\dots,r\}$. We prove that $U_j$ contains no antipodal pair, meaning \begin{align*} U_j\cap\{-x:x\in U_j\}=\varnothing. \end{align*} Suppose instead that $x\in U_j$ and $-x\in U_j$. Since $x\in U_j$, there exists $A\subset P(x)$ with $|A|=k$ and $c(A)=j$. Since $-x\in U_j$, there exists $B\subset P(-x)$ with $|B|=k$ and $c(B)=j$. For every index $i\in[n]$, the inequality $p_i\cdot(-x)>0$ is equivalent to $p_i\cdot x<0$. Hence $P(-x)=N(x)$. Therefore $A\subset P(x)$ and $B\subset N(x)$. The sets $P(x)$ and $N(x)$ are disjoint, because no real number is both positive and negative. Thus $A\cap B=\varnothing$. The sets $A$ and $B$ are disjoint vertices of $KG(n,k)$, so they are adjacent. But $c(A)=c(B)=j$, contradicting the properness of $c$. Therefore no $U_j$ contains an antipodal pair. [guided] Fix a colour $j$. If both $x$ and $-x$ belonged to $U_j$, then the definition of $U_j$ would give two $k$-subsets $A$ and $B$ of $[n]$ with the same colour $j$: the set $A$ is contained in the positive index set $P(x)$, while $B$ is contained in $P(-x)$. The equality $P(-x)=N(x)$ follows directly from \begin{align*} p_i\cdot(-x)>0 \quad\Longleftrightarrow\quad p_i\cdot x<0. \end{align*} Thus $A$ lies among indices with positive dot product against $x$, and $B$ lies among indices with negative dot product against $x$. These two index sets are disjoint, so $A\cap B=\varnothing$. Disjoint $k$-subsets are adjacent vertices in the Kneser graph $KG(n,k)$. A proper colouring cannot assign the same colour to adjacent vertices, but both $A$ and $B$ have colour $j$. This contradiction proves that $U_j$ contains no antipodal pair. [/guided] [/step] [step:Apply the antipodal covering theorem to force at least $d+2$ colours] We use the Lyusternik-Schnirelmann antipodal cover theorem in this standard form: for every integer $d\geq 0$, if $S^d$ is covered by $d+1$ open subsets of $S^d$, then at least one member of the cover contains a pair of antipodal points. The theorem applies because $d=n-2k\geq 0$, the sets $U_1,…,U_r$ are open in $S^d$, and they cover $S^d$. If $r<d+1$, define $U_{r+1},…,U_{d+1}$ to be the empty subset of $S^d$; these added sets are open and contain no antipodal pair. Hence we obtain a cover of $S^d$ by exactly $d+1$ open sets, none of which contains an antipodal pair. This contradicts the Lyusternik-Schnirelmann antipodal cover theorem. Thus no proper colouring of $KG(n,k)$ with at most $d+1$ colours exists, and therefore \begin{align*} \chi(KG(n,k))\geq d+2. \end{align*} Combining this with the explicit colouring gives \begin{align*} \chi(KG(n,k))=d+2=n-2k+2. \end{align*} This proves the theorem. [guided] We have constructed an open cover $U_1,…,U_r$ of $S^d$ from a hypothetical proper colouring with $r\leq d+1$ colours, and we proved that no $U_j$ contains an antipodal pair. The topological theorem now says this is impossible. The Lyusternik-Schnirelmann antipodal cover theorem states that, for every integer $d\geq 0$, every cover of $S^d$ by $d+1$ open subsets has at least one member containing a pair of antipodal points. Its hypotheses are satisfied here because $d=n-2k\geq 0$ and the sets $U_1,…,U_r$ are open in $S^d$ and cover $S^d$. If $r=d+1$, we apply the theorem directly to $U_1,…,U_r$. If $r<d+1$, we pad the cover by defining the additional sets $U_{r+1},…,U_{d+1}$ to be empty. The empty set is open in $S^d$, and it contains no antipodal pair. The padded family still covers $S^d$, because the original family already did. Thus the Lyusternik-Schnirelmann theorem guarantees that one member of the padded cover contains an antipodal pair. This contradicts the previous step: the original sets $U_1,…,U_r$ contain no antipodal pair by properness of the colouring, and the padded empty sets contain no points at all. Therefore a proper colouring with $r\leq d+1$ colours cannot exist. Hence every proper colouring uses at least $d+2$ colours: \begin{align*} \chi(KG(n,k))\geq d+2. \end{align*} The first step constructed a proper colouring with $d+2$ colours, so \begin{align*} \chi(KG(n,k))\leq d+2. \end{align*} Combining the two inequalities yields \begin{align*} \chi(KG(n,k))=d+2=n-2k+2. \end{align*} This is exactly the asserted chromatic number. [/guided] [/step]