Kneser's conjecture states that the chromatic number of the Kneser graph $KG(n,k)$ is $n-2k+2$. A simple proof using topological methods was given by Bárány, and an involved combinatorial proof by Matoušek.
If we only consider the special case $KG(2n,n-1)$, i.e., the vertices are subsets of size $n-1$ of $\{1,2,\dots,2n\}$ and the chromatic number is $2n-2(n-1)+2=4$, is there a simple combinatorial proof for this?
We have found such a proof together with Gábor Tardos while working on the local chromatic number of Kneser graphs and their relaitives. I try to give a detailed sketch.
Let me use the notation KG(2k+2,k) (instead of KG(2n,n-1), I use n for the size of the basic set, that is, n=2k+2). We will actually argue for Schrijver graphs SG(2k+2,k). (SG(n,k) is an induced subgraph of KG(n,k) having the same chromatic number by a result of Schrijver.) Proving that SG(2k+2,k) cannot be properly colored with 3 colors is clearly enough. The vertices of SG(n,k) are the so-called stable k-subsets of the basic n-set, where a k-subset is stable if it does not contain cyclically consecutive elements. (That is, if the basic set is {1,2,...,n}, then A is stable if {i,i+1} is not a subset of A for any i and {n,1} is also not a subset of A.)
The first step is to understand the structure of SG(2k+2,k) which can be visualized very clearly. It can be obtained by some modification of the Cartesian product of the cycle C_{2k+2} and a path P_r where r depends on k, of course, but its actual value will be irrelevant for our argument (though we use that r>1). (The Cartesian product $F\Box G$ is the graph with vertices (u,v), u coming from V(F), v coming from V(G) and (u,v) adjacent to (u',v') if u=u' and (v,v') is an edge of G or v=v' and (u,u') is an edge of F.) So $C_{2k+2}\Box P_r$ is a sort of quadrangular grid on a cylinder consisting of r vertex-disjoint cycles of length (2k+2) each as layers (that one can imagine piled on top of each other where neighboring cycles are joined by a perfect matching in which adjacent vertices of one cycle are matched to adjacent vertices of the other). I imagine these cycles put vertically "on top of each other", so I will refer to the bottom cycle and the top cycle meaning the subgraphs of $C_{2k+2}\Box P_r$ that the vertex subsets {(u,1): u\in V(C_{2k+2}} and {(u,r): u\in V(C_{2k+2}} induce, respectively. Now we modify this gridlike structure to obtain SG(2k+2). For the top cycle we add all edges we can to make it a complete bipartite graph K_{k+1,k+1}. We also make some modification at the bottom cycle but that is different for odd and even k. If k is odd then we connect the opposite points of the bottom cycle. (That is, (1,i) is connected to (1,k+1+i) for every i\in {1,2,...,k+1}.) If k is even, then instead of adding any edges to the bottom cycle, we identify its opposite points. That is, we remove the bottom cycle and substitute it with a cycle with half the length, each vertex of which is connected to two opposite points of the C_{2k+2} in the second layer of the Cartesian product $C_{2k+2}\Box P_r$ in such a way that neighboring vertices of the short cycle are adjacent to neighboring vertices of the double-length cycle in the second layer. It would take longer to give a formal proof that SG(2k+2,k) looks indeed this way, but (hoping that the description above is clear) once you know this it is not hard to verify that this is indeed so. Let me also note what the operation we made with the bottom cycle means coloringwise: In the odd case it clearly means that opposite points of the bottom cycle must be colored differently. If k is even, then its effect to the cycles of higher layers is the same as if we left the bottom cycle having length 2k+2 but we insisted that its opposite vertices must be colored the same color.
We want to show that these graphs have no proper 3-colorings. To do this we define the winding number of a proper 3-coloring of a cycle C_n. Formally we can define it this way. Color C_n properly with colors 0,1,2 (denote the coloring function by c) and now go around the vertices 1,2,..,n,1 in this order putting a label +1 or -1 on each edge (i,i+1) and (n,1) according to whether c(i+1)-c(i)=+1 or -1 mod 3. Now adding all these labels around the cycle we must get a number divisible by 3. Its third is the winding number we wanted to define. (It is simply the number of times the coloring c, which is a graph homomorphism to a triangle winds around the triangle as we go around our C_n. What will matter for our argument is only whether this winding number is zero or non-zero, so the division by 3 is not really needed except for making the origin of the concept clear.)
The proof is obtained by verifying the following facts: 1. The winding number of a proper 3-coloring of the top cycle (that is extended to a complete bipartite graph) is 0. 2. The winding number of the cycle layers in a properly 3-colored Cartesian product C_n\Box P_r must all be equal. 3a. The winding number of a properly 3-colored odd cycle is nonzero. 3b. The winding number of a properly 3-colored C_{2k+2} where k is odd and the color of opposite points cannot be equal is always nonzero.
Indeed, Fact 2 implies that if SG(2k+2,k) is properly 3-colored then the coloring of its top and bottom cycle must have the same winding number. But Fact 1 says the top one must have winding number 0, while Facts 3a and 3b say that the bottom cycle must have nonzero winding number both in the even k and the odd k case, so it cannot be equal to that of the top cycle, contradiction. (In case of even k we have to add that Fact 3a implies that if C_{2k+2} is properly 3-colored so that opposite vertices get the same color then the winding number of this 3-coloring is just twice the winding number of the 3-coloring obtained on the half length cycle when identifying opposite vertices and giving them their common color.)
Now a few words about the proof of the Facts.
Fact 1 is straightforward as one side of a complete bipartite graph must be monochromatic in a proper 3-coloring, so the same number of edge labels in the definition of the winding number will be +1's and -1's and thus they sum up to 0.
Fact 2 is clearly enough to prove for r=2, that is, when we have only two cycle layers. Consider the "elementary" quadrangles on vertices of the form (1,i), (1,i+1),(2,i+1),(2,i), where n+1 is considered to be 1. Fix a proper 3-coloring c and for each such quadrangle go around its edges in the order above labelling them +1 or -1 according to the mod 3 value of the color difference in the given order. Since each quadrangle must have two opposite vertices colored the same color, the sum of these labels for every elementary quadrangle is 0. If we get around all the elementary quadrangles around the cycle C_n, then we take into account every edge of the type {(1,j),(2,j)} once in both directions, while every edge of the type {(1,i),(1,i+1)} once in one direction and every edge of the type {(2,i),(2,i+1)} once in exactly the opposite direction as {(1,i),(1,i+1)}. So the total sum is the sum of labels around the two cycles one traversed in one, the other in the other direction. (The labels on the other edges cancel.) And since the sum for all elementary quadrangles is 0, this total sum is 0, so the sums for the two cycles are the same if they are traversed in the same direction.
Fact 3a is straightforward since an odd number of +1's and -1's cannot sum to 0. Fact 3b is equivalent to say that if k is odd and C_{2k+2} is properly 3-colored so that the winding number of the 3-coloring is 0, then there will be two opposite vertices of the same color. Label the edges of the 3-colored cycle again as in the definition of the winding number. Consider k+1 consecutive edges (a "half cycle"). If the sum of their labels is 0, then we found two opposite points with the same label. Assume the sum is m that is not 0. But we know it should be an even number, since it is the sum of an even number of integers of absolute value 1. Shift our half cycle by one edge (in clockwise direction, say). The sum of labels will become m-2, m, or m+2. Since the winding number is 0, after k+1 shifts it should be -m. But then (since m is even) there must have been a position when it was 0 and that means we had to see two opposite points that are colored the same color.
I hope this sketchy argument is followable, if not then let me know.
Gábor Simonyi
Edit. I accidentally reinvented the wheel and produced the (easy) proof that $KG(2n,n-1)$ is $4$-colourable (but not necessarily $4$-chromatic). I keep it below for those interested, together with a proof that $KG(2n,n-1)$ is not $2$-colourable.
For $i \in [3]$ let $\mathcal{S}_i$ be the subsets of size $n-1$ of $[2n]$ that contain $i$, and let $\mathcal{S}_4$ be the subsets of size $n-1$ of $[2n]$ that are contained in $\{4, \dots, 2n\}$. Now colour an $(n-1)$-subset $X$ of $[2n]$ with colour $i$ if $X \in \mathcal{S}_i$. Note that there may be more than one choice if $X$ contains more than one element from $[3]$, in which case just pick one of the valid choices. This clearly produces a valid $4$-colouring of $KG(2n,n-1)$. To see this note that any two $(n-1)$-subsets of a set of size $2n-3$ must intersect, and for $i \in [3]$ every two sets in $\mathcal{S}_i$ intersect because they each contain $i$.
On the other hand, we show that $KG(2n, n-1)$ is not $2$-colourable by exhibiting an odd cycle. Place the points in $[2n]$ clockwise order around a circle and for each $i \in [2n]$ let $X_i$ be the set containing $n-1$ consecutive points in clockwise order, beginning with $i$.
If $n$ is odd, we claim that $X_1, X_{n}, X_{2n-1}, \dots, X_{1+(n-1)(n-1)}$ is an odd cycle in $KG(2n, n-1)$, where the subscripts are read modulo $2n$. First note that there are $n$ sets in this sequence, and $n$ is odd. So, it suffices to verify that $X_1$ and $X_{1+(n-1)(n-1)}$ are disjoint. To see this, note that $1+(n-1)(n-1) \equiv n+2 \pmod{2n}$, and so $X_{1+(n-1)(n-1)}=X_{n+2}$ which is clearly disjoint from $X_1$.
Similarly, if $n$ is even, $X_1, X_n, X_{2n-1}, X_{n(n-1)}$ is an odd cycle in $K(2n, n-1)$.
