Mathematics

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:

400px-Kneser_graph_KG(5,2).svg

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:

400px-Kneser_graph_KG(5,2).svg_withcol

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.

qkneser_colorless

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:

qkneser_colors

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.

Advertisements

Erdős-Ko-Rado Theorems for Spherical Buildings

Today’s topic combines three of my favorite subjects: Erdős-Ko-Rado theorems (EKR theorems), finite buildings and spectral techniques. All of these topics deserve their own books (and have them, here some examples which I read: Erdos-Ko-Rado Theorems: Algebraic Approaches by Chris Godsil and Karen Meagher, Spectra of Graphs by Andries E. Brouwer and Willem H. Haemers, The Structure of Spherical Buildings by Richard M. Weiss), so I will only touch these topics slightly.

My main aim is to present a variation of the EKR theorem which is motivated by questions about spherical buildings. The variation was recently formulated by Klaus Metsch, Bernhard Mühlherr, and me. If you already know spherical buildings, then you might prefer to read the introduction of our paper instead.

EKR Theorems

Erdős, Ko, and Rado published the following famous result in 1961:

EKR Theorem: Let n \geq 2k. A family \mathcal{F} of pairwise intersecting k-sets of \{ 1, 2, \ldots, n \} satisfies |\mathcal{F}| \leq \binom{n-1}{k-1}. If equality holds and n \geq 2k+1, then \mathcal{F} is the family of all sets that contain one given element.

For n = 2k a characterization is not feasible as there are really many examples. This is an easy exercise.

Variations of this result are central in many areas of combinatorics. This blog post will focus on generalizations of the EKR theorem to structures which are related to finite buildings. Here the story begins with an EKR result due to Hsieh for vector spaces. In the following we denote the the n-dimensional vector space over a field with q elements by \mathbb{F}_q^n and we denote the number of k-spaces in \mathbb{F}_q^n by \binom{n}{k}_q.

EKR Theorem for vector spaces: Let n \geq 2k. A family \mathcal{F} of pairwise intersecting k-spaces of the n-dimensional vector space over the field with q elements satisfies |\mathcal{F}| \leq \binom{n-1}{k-1}_q.

Here the characterization of equality is slightly different and was completed by Godsil and Newman (2006) and Tanaka (2006):

EKR Theorem for vector spaces (equality): If equality holds, then one of the following occurs:

  • \mathcal{F} is the family of all k-spaces that contain one given 1-space.
  • n = 2k and \mathcal{F} is the family of all k-spaces that are contained in one given (2k-1)-space.

Unlike in the set case, here a characterization of the n=2k is feasible. In fact this result provides a first example for an EKR theorem for a spherical building. Let us explore this connection in general.

Spherical Buildings

While I am well-trained to work in specific buildings (vector spaces, polar spaces, a little bit in some exceptional geometries), I am not that well-versed in building theory itself, so I apologize for any imprecise or slightly wrong statements in this section. Defining spherical buildings takes some time (here is Tits original work), so here I will limit myself to a few examples. If you ignore the H’s and I’s in the next picture (which I took from a Wikipedia article), then you see essentially all types of spherical buildings:

640px-Finite_coxeter

There is no need to understand this (I would not say that I do) and I will mostly limit myself to the following example: the vector space \mathbb{F}_q^4 is a spherical building of type A_3 with this diagram: O–O–O. Here we have the following objects:

  1. Subspaces of dimension 1 correspond to the left dot.
  2. Subspaces of dimension 2 correspond to the central dot.
  3. Subspaces of dimension 3 correspond to the right dot.

The important thing here are maximal flags, that is a set \{ V_1, V_2, V_3 \} of subspaces with V_1\subset V_2 \subset V_3 and \dim(V_i) = i (so one of each the three dots). Now we can define a graph with all maximal flags as vertices and two vertices \{ V_1, V_2, V_3 \} and \{ U_1, U_2, U_3 \} are adjacent if we only have to change one subspace to turn \{ V_1, V_2, V_3 \} into \{ U_1, U_2, U_3 \}.

Examples: (here \{ e_1, e_2, e_3, e_4 \} is the standard basis of \mathbb{F}_q^4)

  • \{ \langle e_1 \rangle, \langle e_1, e_2 \rangle, \langle e_1, e_2, e_3 \rangle \} and \{ \langle e_2 \rangle, \langle e_1, e_2 \rangle, \langle e_1, e_2, e_3 \rangle \} adjacent.
  • \{ \langle e_1 \rangle, \langle e_1, e_2 \rangle, \langle e_1, e_2, e_3 \rangle \} and \{ \langle e_1 \rangle, \langle e_1, e_3 \rangle, \langle e_1, e_2, e_3 \rangle \} adjacent.
  • \{ \langle e_1 \rangle, \langle e_1, e_2 \rangle, \langle e_1, e_2, e_3 \rangle \} and \{ \langle e_2 \rangle, \langle e_2, e_3 \rangle, \langle e_1, e_2, e_3 \rangle \} are not adjacent, but at distance 2 (\{ \langle e_2 \rangle, \langle e_1, e_2 \rangle, \langle e_1, e_2, e_3 \rangle \} is adjacent to both).
  • \{ \langle e_1 \rangle, \langle e_1, e_2 \rangle, \langle e_1, e_2, e_3 \rangle \} and \{ \langle e_2 \rangle, \langle e_2, e_3 \rangle, \langle e_2, e_3, e_4 \rangle \} are at distance 3. Here is one path between these two flags: \{ \langle e_1 \rangle, \langle e_1, e_2 \rangle, \langle e_1, e_2, e_3 \rangle \}\{ \langle e_2 \rangle, \langle e_1, e_2 \rangle, \langle e_1, e_2, e_3 \rangle \}\{ \langle e_2 \rangle, \langle e_2, e_3 \rangle, \langle e_1, e_2, e_3 \rangle \}\{ \langle e_2 \rangle, \langle e_2, e_3 \rangle, \langle e_2, e_3, e_4 \rangle \}.
  • \{ \langle e_1 \rangle, \langle e_1, e_2 \rangle, \langle e_1, e_2, e_3 \rangle \} and \{ \langle e_4 \rangle, \langle e_3, e_4 \rangle, \langle e_2, e_3, e_4 \rangle \} are at distance 6 (Exercise!). This is the largest distance between two vertices in this graph (the vertices are “opposite”).

So what does this have to EKR theorems? We have a graph with distances. If we limit ourselves to so-called partial flags of type { 2 }, that are just 2-spaces of \mathbb{F}_q^4, then we can define a similar  graph: the vertices are the 2-spaces and two 2-spaces are adjacent if they intersect in a 1-space. In an abuse of notation that hopefully makes the connection to the graph of maximal flags more obvious:

Examples: 

  • \{ \ast, \langle e_1, e_2 \rangle,\ast \} and \{ \ast, \langle e_2, e_3 \rangle,\ast \} are adjacent because the 2-spaces intersect in \langle e_2\rangle, but also — when we fill in the *’s — we see that the maximal flags that contain \langle e_1, e_2 \rangle and \langle e_2, e_3 \rangle are not that far apart from each other. If we do this in the right way, both maximal flags will be adjacent in our graph of maximal flags, e.g. \{ \langle e_2 \rangle, \langle e_1, e_2 \rangle, \langle e_1, e_2, e_3\rangle \} and \{ \langle e_2\rangle, \langle e_2, e_3 \rangle, \langle e_1, e_2, e_3\rangle \}.
  • \{ \ast, \langle e_1, e_2 \rangle,\ast \} and \{ \ast, \langle e_3, e_4 \rangle,\ast \} are non-adjacent. If we fill in the *’s, then the closest distance which we can achieve in our graph of maximal flags is 4, e.g. with \{ \langle e_2 \rangle, \langle e_1, e_2 \rangle,\langle e_1, e_2, e_3 \rangle \} and \{ \langle e_3 \rangle , \langle e_3, e_4 \rangle,\langle e_2, e_3, e_4 \rangle \}.

So let’s say that if two vertices are at maximal distance from each other, then they are opposite (so at distance 6 for the maximal flags, while at distance 2 when we only consider 2-spaces). Then we can ask the following question:

What is the largest set \mathcal{F} of pairwise non-opposite vertices in the graphs of flags of type { 2 } in A_3?

We already know the answer to this question as it is just the EKR theorem for vector spaces in the case of 2-spaces, so we have at most \binom{2}{1}_q such vertices and in the case of equality one of the following occurs:

  • \mathcal{F} is the family of all 2-spaces containing a fixed 1-space U.
  • \mathcal{F} is the family of all 2-spaces in a fixed 3-space U'.

Let us assume that the first case occurs. Let W \neq U be another 1-space. Then (using a reasonable definition of distance) one can see that W is never closer to a member of \mathcal{F} than U. This means that \{ U \} is a center of \mathcal{F} and it relates to the center conjecture by Tits (see The center conjecture for non-exceptional buildings by Mühlherr and Tits):

Center Conjecture: (see the relevant literature for a precise statement) A convex subcomplex \mathcal{F} of a spherical building \Delta (read: convex set \mathcal{F} of vertices in the graph of maximal flags) satisfies one of the following:

  1. For each simplex A in \mathcal{F} there is a simplex B in \mathcal{F} which is opposite to A in \Delta.
  2. The group \text{Stab}_{\text{Aut}(\Delta)}(\mathcal{F}) fixes a non-trivial subcomplex of \mathcal{F}, that is \mathcal{F} has a center.

What is the connection to the EKR theorem? In EKR theorem we do not allow vertices to be opposite to each other, so we are not in case 1. We do not assume convexity or the existence, but it usually turns out that if\mathcal{F} has maximum size, then it is convex and has a center. So EKR theorems for spherical buildings and the center conjecture are related.

What I still have to provide is a definition of the EKR problem for spherical buildings. If we label the vertices of the diagram of our geometry (as in the picture above), then we say that a subset of a maximal flag has type J if only vertices of type J are used. So for maximal flags in A_3 we have flags of type J = \{ 1, 2, 3 \}, for 2-spaces we have J = \{ 2 \}, and if we only take pairs of incident 1- and 3-spaces, then we have J = \{ 1, 3 \}. Klaus Metsch, Bernhard Mühlherr, and I recently defined the EKR problem in this setting as follows:

EKR Problem for Spherical Buildings: Let \Delta be a spherical building. Let J be a type of a flag in \Delta.

  1. What is the largest size b of a family of flags of type J which are pairwise non-opposite?
  2. Classify all families of flags of type J with pairwise non-opposite flags of size b.

In particular, the question is if the largest examples have a center. This is usually, but not always the case.

What is known?

Vector Spaces: Type A_n

We already established that the EKR problem is solved for k-spaces vector spaces \mathbb{F}_q^{n+1}, that are buildings of type A_{n} with flags of type \{ k \}. Then there are cases that are easy, e.g. flags of type { 1, 2 }. A few more sporadic cases are known, for example:

  • Flags of type { k } for n+1 \geq 2k+1 due to Hsieh. The center is a flag of type { 1 }.
  • Flags of type { k } for n+1 \leq 2k due to Frankl and Wilson (bound), and Tanaka (classification). The center is a flag of type { t }, where t depends on n and k.
  • Flags of type { 1, n } due to Blokhuis, Brouwer, Cicek. (Diagram with 1 and n big: O–o–o–…–o–o–O)
  • Flags of type { 2, 3 } for \mathbb{F}_q^5 due to Blokhuis and Brouwer. (Diagram with 2 and 3 big: o–O–O–o)
  • Flags of type { 1, 3 } for \mathbb{F}_q^5 due to Blokhuis, Brouwer, and Szönyi. (Diagram: O–o–O–o)

Of course there are many more subsets of n elements and much work can be done here. The classification often results in surprising examples, for example for flags of type { 2, 3 } we have one of these examples:

Fix a 1-space P, 2-space L, a 3-space Q, and a 4-space S.

  1. Take all flags ( A, B ) (of type { 2, 3 }) with B \subseteq S together with one of the following: (a) all flags (A, B) with  A = B \cap S and P \subseteq A or (b) all flags (A, B) with  A = B \cap S and A \subseteq Q.
  2. Take all flags ( A, B ) (of type { 2, 3 }) with P \subseteq A together with one of the following: (a) all flags (A, B) with  B = \langle A, P \rangle and B \subseteq S or (b) all flags (A, B) with  B = \langle A, P \rangle and P \subseteq L.

Attention: Daniel Werner, a PhD student of Klaus Metsch, works on some of the open cases for his PhD. So please contact them so that you are not colliding with Daniel’s work.

“Normal” Polar Spaces: Type B_n/C_n

Polar spaces are more complicated than vector spaces, so less is known. I follow the notation of the Wikipedia article in the following.

  • Flags of type { 1 } are trivial to solve. (Diagram: O–o–…–o–o=o)
  • Flags of type { 2 } was recently solved by Metsch (submitted).
  • Flags of type { n }: Tight bound except for some Hermitian polar spaces are due to Stanton. There the classification of the largest examples was done by Pepe, Storme and Vanhove. For the Hermitian polar spaces, H(2n-1, q^2), n odd, the asymptotically best bound is due to Metsch and me (see Metsch for the best known bound). So here the problem is partially open.

To my knowledge other cases are still open. I want to point out that the classification is very interesting, e.g. for flags of type { 3 } in Q(6, q) there are exactly three different types of largest families.

Hyperbolic Polar Spaces: Type D_n

For hyperbolic polar spaces things are slightly different. Their diagram is already different as B_n looks like O–O–O–…–O=O, while D_n looks like o–o–o–…–o–o<_O^O. Here is the diagram of D_6:

D6_small

One can embed this geometry in the vector space \mathbb{F}_q^{2n} where the dots 1, 2, 3, and 4 correspond to certain 1-, 2-, 3-, and 4-dimensional subspaces, while the dots 5 and 6 correspond to two types of 6-dimensional subspaces. Here the situation is as follows:

  • Flags of type { 1 } are again trivial.
  • Flags of type { 2 } due to Metsch (submitted).
  • Flags of type { n-1 } and { n } for n even due to Stanton (bound) and Pepe, Storme and Vanhove (classification).
  • Flags of type { n-1, n } (this are just (n-1)-dimensional subspaces) for n even due to Metsch, Mühlherr and me.

Exceptional Geometries: e.g. G_2, F_4, E_6, E_7, E_8

For other buildings such as generalized hexagons and generalized octagons, it is easy to determine the largest examples. I was told that a few more cases for exceptional geometries are solved, but these are not yet publically announced, so I cannot comment on them.

Techniques

I want to finish by commenting on the two techniques that are used to solve EKR problems in the mentioned settings. Many of the results (Frankl–Wilson, Tanaka, Stanton, Pepe–Storme–Vanhove, I.–Metsch, I.–Metsch–Mühlherr …) use some variation of Hoffman’s ratio bound on independent sets in a graph which is as follows in its simplest form:

Theorem: Let \Gamma be a r-regular graph on v vertices and smallest eigenvalue \lambda (of the adjacency matrix of \Gamma). Then an independent set in \Gamma has at most size v/(1-r/\lambda).

To use this for EKR problems, one takes flags of type J as vertices and two vertices are adjacent when they are opposite. Then an independent set is a set of pairwise non-opposite flags.

For some other results such (Hsieh for vector spaces, Blokuis–Brouwer, Blokhuis–Brouwer–Cicek, Metsch, …) elementary geometric proofs were used and seem to be more succesful.

High-Dimensional Combinatorics

At the time of writing I am based at the Hebrew University at Jerusalem and the year on Geometric, Topological and Computational Aspects of High-Dimensional Combinatorics is happing here, so let me finish with this remark: The stated problem is about finding the largest family of subcomplexes of a “certain type” in a abstract simplicial complex such that the elements of the family are pairwise “close” too each other. There are certainly other settings beyond spherical buildings in which this question is interesting.

Acknowledgements: I would like to thank Anurag Bishnoi and Karen Meagher for their comments on a draft of this post. Of course all mistakes are my fault.