Austin Ulrigg
← Writing
Expository · July 2026

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 nn books, and consider all of the ways to choose kk of them (where n≥2kn \geq 2k). If you are tasked with sorting these kk-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+2n-2k+2. His sorting method was as follows. Number the books 11 through nn. For each ii from 11 to n−2k+1n-2k+1, create a group out of every subset whose lowest-numbered book is book ii. Any two subsets in group ii both contain book ii, so no two of them are disjoint. The subsets that are left are exactly the ones whose lowest-numbered book is n−2k+2n-2k+2 or higher. Thus, they are entirely from the last 2k−12k-1 books. Two disjoint subsets of size kk would have 2k2k total different books between them, and only 2k−12k-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+1n-2k+1 groups, plus one for the leftovers, so

n−2k+2.n-2k+2.

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 kk-element subset, and put an edge between two subsets exactly when they are disjoint. We call this graph the Kneser graph K(n,k)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)K(n,k) and a sorting of every subset into tt valid groups is a coloring of K(n,k)K(n,k) with tt colors. Kneser's conjecture is therefore χ(K(n,k))=n−2k+2\chi(K(n,k))=n-2k+2.

For example, when k=1k=1, any two different subsets are disjoint, so K(n,1)K(n,1) is the complete graph KnK_n. When n=2kn=2k, each subset is disjoint only from its complement, so K(2k,k)K(2k,k) is a perfect matching. K(5,2)K(5,2) is the Petersen graph, drawn in Figure 1(a).

The Petersen graph with vertices labeled by 2-element subsets of {1,...,5}.
(a) K(5,2)K(5,2), the Petersen graph
The Desargues graph drawn as two nested decagons.
(b) H(5,2)H(5,2), the Desargues graph
Figure 1. Two graphs made of subsets.

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 SdS^d to Rd\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 kk-subsets have been sorted into m=n−2k+1m = n-2k+1 groups. Place the numbers 1,…,n1,\dots,n on the sphere SmS^m as points in general position, meaning no hyperplane through the center touches more than mm of them. Every point xx on the sphere has an open hemisphere H(x)H(x) centered at it. For each group ii, let UiU_i be the set of points xx where H(x)H(x) contains some full subset from group ii. Each UiU_i is open. Let FF be the set of remaining points, whose hemispheres contain at most k−1k-1 of our points. FF is closed. Together, these m+1m+1 sets cover the whole sphere.

A sphere split by a dashed equator into two shaded hemispheres H(x) and H(-x), with antipodal points x and -x and scattered points.
Figure 2. The sphere, the equator, and the two hemispheres.

Now, a theorem similar to Borsuk–Ulam says that if SmS^m is covered by m+1m+1 sets, each of them open or closed, then one of the sets contains two antipodal points xx and −x-x. If that set is some UiU_i, then H(x)H(x) and H(−x)H(-x) each contain a subset from group ii. Because opposite hemispheres are disjoint, so group ii contains two disjoint subsets, a contradiction. If instead the set is FF, then the two hemispheres contain at most 2k−22k-2 points in total, so that at least n−2k+2=m+1n-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+1m+1 points on such a hyperplane, this is also a contradiction. This is basically the whole proof. 1

Intersecting families

A group where every two subsets share a book is called an intersecting family. We can also ask how large one of these can be. In the graph, this is the independence number of K(n,k)K(n,k).

Erdős, Ko, and Rado proved in 1938, and published in 1961, that an intersecting family has at most (n−1k−1)\binom{n-1}{k-1} subsets, and that when n>2kn > 2k the only families this large are the ones where every subset contains the same book. This was before Kneser's exercise, but it gives the independence number of K(n,k)K(n,k).

The bipartite Kneser graphs

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

H(5,2)H(5,2), shown in Figure 1(b), is also called the Desargues graph. Desargues' theorem says that if the three lines joining matching corners of two triangles meet at one point, then the three points where matching sides cross lie on one line (Figure 3). Drawing this gives ten points and ten lines, with three points on each line and three lines through each point. H(5,2)H(5,2) has a vertex for each point and each line, and an edge when the point is on the line.

Two triangles in perspective from a point O, with the three crossings of corresponding sides lying on a dashed line.
Figure 3. Desargues' theorem.

The middle levels graph

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

A hexagon whose vertices alternate between the one-element and two-element subsets of {1,2,3}.
Figure 4. The middle levels graph for k=1k=1.

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 ↩
← Back to Writing