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 books, and consider all of the ways to choose of them (where ). If you are tasked with sorting these -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 . His sorting method was as follows. Number the books through . For each from to , create a group out of every subset whose lowest-numbered book is book . Any two subsets in group both contain book , so no two of them are disjoint. The subsets that are left are exactly the ones whose lowest-numbered book is or higher. Thus, they are entirely from the last books. Two disjoint subsets of size would have total different books between them, and only books remain available. Thus no two of the leftovers are disjoint, and can all be placed into one final group together. This gives 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 -element subset, and put an edge between two subsets exactly when they are disjoint. We call this graph the Kneser graph . 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 and a sorting of every subset into valid groups is a coloring of with colors. Kneser's conjecture is therefore .
For example, when , any two different subsets are disjoint, so is the complete graph . When , each subset is disjoint only from its complement, so is a perfect matching. is the Petersen graph, drawn in Figure 1(a).
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 to 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 -subsets have been sorted into groups. Place the numbers on the sphere as points in general position, meaning no hyperplane through the center touches more than of them. Every point on the sphere has an open hemisphere centered at it. For each group , let be the set of points where contains some full subset from group . Each is open. Let be the set of remaining points, whose hemispheres contain at most of our points. is closed. Together, these sets cover the whole sphere.
Now, a theorem similar to Borsuk–Ulam says that if is covered by sets, each of them open or closed, then one of the sets contains two antipodal points and . If that set is some , then and each contain a subset from group . Because opposite hemispheres are disjoint, so group contains two disjoint subsets, a contradiction. If instead the set is , then the two hemispheres contain at most points in total, so that at least points lie on the equator between them, and the equator spans a hyperplane through the center. Because general position does not allow for 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 .
Erdős, Ko, and Rado proved in 1938, and published in 1961, that an intersecting family has at most subsets, and that when 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 .
The bipartite Kneser graphs
The bipartite Kneser graph , again with , has the -element subsets of on one side and the -element subsets on the other, with an edge between and whenever . A subset is contained in exactly when is disjoint from the complement of , and the complement of is itself a -element subset. So, by taking complements on one of the sides, we can see that is the bipartite double cover of .
, 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. has a vertex for each point and each line, and an edge when the point is on the line.
The middle levels graph
When , the sides of are the -subsets and -subsets of a -element set. These are the two middle layers of the cube of all subsets, so is called the middle levels graph. When it is a hexagon (Figure 4), and when 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.
- besides the topology ↩