Kneser's Exercise

In 1955, Martin Kneser published an exercise in the journal of the German Mathematical Society. The exercise turned out to be much more difficult than Kneser expected and was unsolved for twenty-three years afterward. Because of this, I am not sure whether we should call it a good exercise or a bad one, but I will say good because I like it.

The exercise

The problem was the following. Suppose you have a shelf of $n$ books, and consider all of the ways to choose $k$ of them (where $n \geq 2k$). If you are tasked with sorting these $k$-element subsets into groups, so that no group contains two disjoint subsets, that is, so that any two subsets in the same group share a book, what is the least number of groups you need?

Kneser's idea was that the least number of groups was $n-2k+2$. His sorting method was as follows. Number the books $1$ through $n$. For each $i$ from $1$ to $n-2k+1$, create a group out of every subset whose lowest-numbered book is book $i$. Any two subsets in group $i$ both contain book $i$, so no two of them are disjoint. The subsets that are left are exactly the ones whose lowest-numbered book is $n-2k+2$ or higher. Thus, they are entirely from the last $2k-1$ books. Two disjoint subsets of size $k$ would have $2k$ total different books between them, and only $2k-1$ books remain available. Thus no two of the leftovers are disjoint, and can all be placed into one final group together. This gives $n-2k+1$ groups, plus one for the leftovers, so

However, Kneser was not able to prove that no other sorting uses fewer groups.

The graph

To attempt solving the problem, one could think of creating the following graph. Make one vertex for every $k$-element subset, and put an edge between two subsets exactly when they are disjoint. We call this graph the Kneser graph $K(n,k)$. Two vertices are joined by an edge exactly when a sorting must place them in separate groups. Equivalently, a valid group is an independent set of $K(n,k)$ and a sorting of every subset into $t$ valid groups is a coloring of $K(n,k)$ with $t$ colors. Kneser's conjecture is therefore $\chi(K(n,k))=n-2k+2$.

For example. When $k=1$, any two distinct subsets are disjoint, so $K(n,1)$ is the complete graph $K_n$. When $n=2k$, each subset is disjoint from exactly one other, namely its complement, so $K(2k,k)$ is a perfect matching. $K(5,2)$, drawn in Figure 1(a), is the Petersen graph, which is also the standard counterexample to nearly everything. The Petersen graph needs exactly $3 = 5-4+2$ colors, so the conjecture holds there as well.

(a) $K(5,2)$, the Petersen graph

(b) $H(5,2)$, the Desargues graph

Twenty-three years, then topology

The conjecture was finally proven in 1978 by László Lovász (Lovász, 1978). Lovász used the Borsuk–Ulam theorem: every continuous map from the sphere $S^d$ to $\mathbb{R}^d$ must send some pair of antipodal points to the same value. Bárány found a much shorter proof the same year, and in 2002 Joshua Greene found an even shorter one, so short that we include a sketch of it here.

Suppose that the $k$-subsets have been sorted into $m = n-2k+1$ groups. Place the numbers $1,\dots,n$ on the sphere $S^m$ as points in general position, meaning no hyperplane through the center touches more than $m$ of them. Every point $x$ on the sphere has an open hemisphere $H(x)$ centered at it. For each group $i$, let $U_i$ be the set of points $x$ where $H(x)$ contains some full subset from group $i$. Each $U_i$ is open. Let $F$ be the set of remaining points, whose hemispheres contain at most $k-1$ of our points. $F$ is closed. Together, these $m+1$ sets cover the whole sphere.

Now, a theorem similar to Borsuk–Ulam says that if $S^m$ is covered by $m+1$ sets, each of them open or closed, then one of the sets contains two antipodal points $x$ and $-x$. If that set is some $U_i$, then $H(x)$ and $H(-x)$ each contain a subset from group $i$. Because opposite hemispheres are disjoint, so group $i$ contains two disjoint subsets, a contradiction. If instead the set is $F$, then the two hemispheres contain at most $2k-2$ points in total, so that at least $n-2k+2 = m+1$ points lie on the equator between them, and the equator spans a hyperplane through the center. Because general position does not allow for $m+1$ points on such a hyperplane, this is also a contradiction. This is basically the whole proof. ¹

Intersecting families

We can also consider the same question but require that every two subsets within a group overlap. This is called an intersecting family. The interesting question becomes how large such a group can be. In terms of the graph, this is the independence number of $K(n,k)$.

The Erdős–Ko–Rado theorem, from 1961, says that no intersecting family beats the star, and that when $n > 2k$, every intersecting family of maximum size is a star. This was proven before the Kneser graph was even first conceptualized, but when one considers the Kneser graphs, it is clear that this theorem computes their independence number.

The bipartite Kneser graphs

The bipartite Kneser graph $H(n,k)$, again with $n > 2k$, has the $k$-element subsets of $\{1,\dots,n\}$ on one side and the $(n-k)$-element subsets on the other, with an edge between $A$ and $B$ whenever $A \subseteq B$. A subset $A$ is contained in $B$ exactly when $A$ is disjoint from the complement of $B$, and the complement of $B$ is itself a $k$-element subset. So, by taking complements on one of the sides, we can see that $H(n,k)$ is the bipartite double cover of $K(n,k)$.

$H(5,2)$ is shown in Figure 1(b). It is also called the Desargues graph. Girard Desargues was a French geometer who proved a classical theorem. It states that if two triangles are positioned so that the three lines drawn through their corresponding vertices all contain one common point, then the three points where their corresponding sides cross all lie on one common line (Figure 3). Drawing that theorem produces ten points and ten lines, with three points on every line and three lines through every point. We see that $H(5,2)$ records which points lie on which lines. If you read my post about matroids, you have now seen that this is the second time projective geometry has shown up. I do not know what to tell you.

The middle levels graph

When $n = 2k+1$, the sides of $H(2k+1,k)$ are the $k$-subsets and $(k+1)$-subsets of a $(2k+1)$-element set. These are the two middle layers of the cube of all subsets, so $H(2k+1,k)$ is called the middle levels graph. When $k=1$ it is a hexagon (Figure 4), and when $k=2$ it is the Desargues graph from Figure 1(b).

A famous conjecture about the middle levels graph was whether or not it always has a Hamiltonian cycle. If such a cycle existed, then walking along it would list every one of these subsets exactly once. Each subsequent step of the walk would change from the previous by adding or removing only a single element. In computer science, such a list is called a Gray code, which turns out to be useful for many things.

In 1991, Simpson conjectured that every bipartite Kneser graph has a Hamiltonian cycle, and Mütze and Su proved it years later.(Mütze and Su, 2017). The Kneser graphs themselves were proven to have a Hamiltonian cycle in 2023, with exactly one exception (Merino, Mütze, and Namrata, 2023). The one exception is, of course, the Petersen graph.

Why I bring them up

I have a question about the bipartite ones myself. But it deserves its own post.

1. besides the topology ↩