The chromatic number of the Kneser graphs and the q-Kneser graphs

This year is László Lovász‘s 70th birthday and I went to his birthday conference, so a blog post about one of his famous results seems to be appropriate: the chromatic number of the Kneser graph.

Let $ \Gamma$ be a graph with a vertex set $ V$ and an adjacency relation $ \sim$. A coloring of $ \Gamma$ is a map from $ V$ from $ V$ to a set of colors $ C$ such that no pair of adjacent vertices gets mapped to the same element of $ C$. The chromatic number of $ \Gamma$ is the smallest number of colors needed to color $ \Gamma$. One of the nicest graphs to investigate is the Kneser graph: Here $ V$ consists of all subsets of $ \{ 1, 2, \ldots, n \}$ of size $ k$ and two vertices are adjacent if the corresponding $ k$-sets are disjoint. For $ k=2$ and $ n=5$, this is the famous Petersen graph:

It is well-known that we can color the Petersen graph with 3 colors, but not with 2 (because the graph contains 5-cycles), so the chromatic number is 3:

When we increase $ n$ by one to $ n = 6$, then we need $ 4$ colors. Now if we increase $ k$ from $ 2$ to $ 3$, then the resulting graph is bipartite an the chromatic number is obviously $ 2$. In general: When we increased $ n$ by one, then the chromatic number increased by one, and when we increased $ k$ by one, then the chromatic number decreased by $ 2$. Martin Kneser conjectured that the Kneser graph always behaves like this (a long as $ n \geq 2k$), so that the chromatic number is $ n – 2k + 2$. This was shown by Lovasz in 1978. Nowadays many different proofs of the Kneser’s conjecture are known. The significance of Lovasz’s result lies in the fact (besides solving the problem) that it relies on a topological statement, the Borsuk-Ulam theorem, and, therefore, gave rise to topological proofs in combinatorics.

One can define a $ q$-analog of the Kneser graph: Here our vertex set is the set of $ k$-subspaces of a finite vector space of dimension $ n$ over a finite field of size $ q$. Two vertices are adjacent if and only if their intersection is a subspace of dimension $ 0$.

For $ n \geq 2k+1$ Blokhuis, Brouwer, Chowdhury, Frankl, Mussche, Patkós, and Szőnyi showed that the correct answer is $ (q^{n-k+1}-1)/(q-1)$. Their proof does not involve $ q=2$ and $ n=2k+1$, but one can fix this with other techniques. In another paper Blokhuis, Brouwer and Szönyi showed that for $ n=2k$ (remember, this was a boring question for the set case!) the answer is $ q^k+q^{k-1}$ as long as $ k < q \log q – q$. I recently showed that one can drop the condition on $ q$ and just require $ q \geq 5$ (most likely $ q \geq 3$, but this I could not show). In the following I want to spent some time on explaining how the proof by Blokhuis et al. works. For $ q=2$, $ k = 2$, and $ n = 4$ the following image gives an idea on how the structure of $ 2$-spaces in graph looks like. The vertices are the lines and two lines are adjacent when they do not meet (so intersect in dimension 0). Our picture here is incomplete as we only show a $ 3$-space, a Fano plane, and some of the lines meeting it.

For any coloring the vertices with the same color are pairwise non-adjacent, so they form an independent set. Hence, the maximum size $ \alpha$ of an independent set of a graph with $ v$ vertices gives the lower bound $ v/\alpha$ on the chromatic number of the graph (at least for a vertex-transitive graph). Now it could be that we are not using our largest independent sets (or subsets of them) for all of our colors in the graph, but then our lower bound on the chromatic number gets better than $ v/\alpha$. One standard way of determining the chromatic number of a nice graph (such as the $ q$-Kneser graph) is to show two things: (1) One characterizes the structure of the largest independent sets. (2) One shows that all independent sets, which are not contained in the largest ones, are much smaller than the largest independent sets. If (1) and (2) are both true, then we are in a good situation: As soon as we use independent sets which are not the largest ones, then, due to (2), our bound on the chromatic number gets much better, so we are good.

In the $ q$-Kneser graph, even for $ n=2k$, the situation is good. The largest independent sets (sets of pairwise intersecting $ k$-spaces) have size $ \genfrac{[}{]}{0pt}{}{2k-1}{k-1} := \prod_{i=1}^{k-1} \frac{q^{2k-i}-1}{q^i-1} \sim q^{k(k-1)}$ — this is the number of $ k$-spaces containing one fixed $ 1$-space or lying in one fixed $ (2k-1)$-space — , while the the second largest maximal independent set is smaller by a factor of $ \sim q^{-1}$ as long as $ q$ is a bit larger than $ 2$. For an example take $ k=2$. We can easily color the $ q$-Kneser graph in $ q^2+q$ colors as follows (we will use projective notation for this, so a $ 1$-space is a point, a $ 2$-space a line, and a $ 3$-space a plane): Fix a plane $ \pi$. Take a line $ \ell$ in $ \pi$. For each plane $ \pi’$ through $ \ell$ with $ \pi \neq \pi’$ we assign one color to all lines in that plane. There are $ q$ planes like this. This assigns a color to all lines not in $ \pi$ which meet $ \ell$. We still have to color all lines which meet $ \pi$ in a point in $ \pi \setminus \ell$. There are $ q^2$ such points. For each of these we assign a color to all lines incident with that point. Now we have used $ q^2+q$ colors and all lines got (at least) one color as they all meet $ \pi$. Here is a picture for $ q=2$:

Now suppose that we find a coloring with less than $ q^2+q$ colors. If we only use points and hyperplanes for coloring, then suppose that there is a line $ \tilde{\ell}$ which is not colored by any plane and colored by exactly one point $ \tilde{p}$. There are $ q^3+q^2$ lines $ \mathcal{L}$ which meet $ \tilde{\ell}$ in a point, but do not contain $ \tilde{p}$. A point not in $ \tilde{\ell}$ colors at most $ q$ lines of $ \mathcal{L}$, the first hyperplane containing a point $ r \in \tilde{\ell}$ colors at most $ q+1$ lines of $ \mathcal{L}$, while each subsequent hyperplane on $r$ colors at most $ q$ lines of $ \mathcal{L}$. If we color $ \mathcal{L}$ with $ x$ points and $ y$ hyperplanes, then this gives that we color at most $ qx + qy + q$ elements of $ \mathcal{L}$ with these. Hence, $ x+y \geq q^2+q-1$. Therefore, we need $ q^2+q$ colors in total. In this special case, there are no other maximal independent sets (one could say, the next smallest example has size 0), so the chromatic number is $ q^2+q$. For larger $ k$, this is not the case and the complicated part is to bound size of the second largest intersecting family.

Follow the blog!