Kneser subgraph with high chromatic number

Question

For positive integers $n\geq 2k$, it is known that the chromatic number of the Kneser graph $K_{n,k}$ is $n-2k+2$. Moreover, the Schrijver graph $S_{n,k}$ (definition in the same link), which is a subgraph of $K_{n,k}$, also has chromatic number $n-2k+2$. The number of vertices of $S_{n,k}$ is $\binom{n-k+1}{k}$.

Is it known whether there is a subgraph of $K_{n,k}$ with chromatic number $n-2k+2$ whose number of vertices is polynomial in $n$ and $k$?

Answer 1

The general answer is no, at least when $n$ is close to $2k$.

Theorem 3 in this paper shows that a graph with odd girth $\geq 2d+1$ and chromatic number $>m$ contains more than $$ \frac{(m+d)(m+d+1)\dots(m+2d-1)}{2^{d-1}d^d} $$ vertices. The parameters for the Kneser graph $K_{n,k}$ are $m=n-2k+1$ and $d=\bigl\lceil\frac k{n-2k}\bigr\rceil$, so, say, for $n\approx 2k+\sqrt k$ the bound is already exponential in $\sqrt k$.