finite geometry

Translating Terminology: Equitable Partitions and Related Concepts

Permutation Groups, Analysis of Boolean Functions, Finite Geometry, Coding Theory and Algebraic Graph Theory

Important mathematical concepts get reinvented many times. In my recent work with Yuval Filmus we explored objects that are called (in random ordering) Boolean degree 1 functions, Cameron-Liebler line classes, equitable partitions, completely regular strength 0 codes with covering radius 1, intriguing sets, perfect colorings, sets with dual width 1, tactical decompositions or tight sets — all depending on the context and who you ask. While the article with Yuval explains to some extend how these notions connect, a research article does not seem to be the right format to explain all concepts in sufficient detail. This post tries to amend this. It also prepares a future post which will elaborate my research with Yuval in more detail.

Algebraic Graph Theory

Let X be a graph on v vertices V(X). The adjacency matrix A of X is the v \times v matrix indexed by the vertices of X such that A_{xy} = 1 if x and y are adjacent and A_{xy} = 0 otherwise. In the following we stick to the assumption that X is a regular graph, so every vertex has the same number of neighbors. This is equivalent to saying that the all-ones vector j is an eigenvector of A. The matrix A is symmetric, so we find many other eigenspaces over the reals and this is what this post is about.

Three Examples

We will mostly work with the following three examples throughout this document.

Example 1

Let J(n, k) be the graph with the k-element subsets of an n-element set as vertices. Two vertices are adjacent if they meet in k-1 elements. This is the Johnson graph.

Example 2

Let q be a prime power. Let J_q(n, k) be the graph with the k-spaces of an n-dimensional vector space over \mathbb{F}_q as its vertices. Two vertices are adjacent if they meet in a subspace of dimension k-1. This is the Grassmann graph or q-Johnson graph.

Example 3

Let \overline{D}_n be the graph with the elements of the symmetric group S_n as vertices. We see S_n as a permutation group acting naturally on n. Two vertices x, y are adjacent if x y^{-1} has exactly n-2 fix points. This graph is known as the transposition graph. I do not know if this graph has some special name, but the graph on the same set of vertices, where two vertices are adjacent if x y^{-1} has no fix points, is called derangement graph.

Eigenspaces

All eigenspaces of the first two examples were described in Philippe Delsarte’s PhD thesis in 1973. The third example is a Cayley graph on S_n, which means that it is well-known that one can obtain its eigenvalues from the character table (so the representation theory) of S_n.

Equitable Partitions

An equitable partition is a partition of V(X) into m parts X_1 + \ldots + X_m such that there exist constants b_{ij} such that every vertex in X_i has exactly v_{ij} neighbors in X_j. Another word for equitable partition is perfect coloring. The central property of equitable partitions is the following: The eigenvalues of the matrix B = ( b_{ij} )_{i,j} are also eigenvalues of the adjacency matrix A. The existence of equitable partitions is a question that is investigated on its own for many interesting graphs, but I believe that the notion was invented as an easy way of determining eigenvalues of a graph.

Warning: The term equitable partition is also used by Janos Pach for a completely different concept which I will not go into. For example this paper talks about this different usage of the word.

Example 4

Let X_1 the set of all k-sets containing 1 and X_2 the set of all the remaining k-sets. Then |X_1| = \binom{n-1}{k-1} and |X_2| = \binom{n-1}{k}. It is an easy exercise to verify that this is an equitable partition with b_{11} = (k-1)(n-k), b_{12} = n-k, b_{21} = k, and b_{22} = k(n-k-1). The eigenvalues of B are k(n-k) (this is the degree of the graph) and k(n-k)-n — the second largest eigenvalue of A.

Example 5

Let X_1 be the family of all k-sets containing 1 and 2, X_2 the family of all k-sets containing 1 or 2, and X_3 the remaining k-sets. Again, we can easily verify that this is an equitable partition. This time b_{11} = (k-2)(n-k), b_{12} = 2(n-k), b_{13} = 0, b_{21} = k-1, b_{22} = (k-1)(n-k-1) + 1, b_{23} = n-k-1, b_{31} = 0, b_{32} = 2k, b_{33} = k(n-k-2). The eigenvalues of B are then k(n-k), k(n-k)-n and k(n-k) - 2n.

You see the pattern? So let’s jump ahead.

Example 6

Let X_j be the family of all k-sets meeting \{ 1, \ldots, k \} in k-j elements. Then X_0, X_1, \ldots, X_k is an equitable partition. This partition yields directly all the eigenvalues of the Johnson graph which are k(n-k)-ni for i = 0, \ldots, k.

Distance-regular graphs

You might have noticed that the last example just partitioned the vertices of J(n, k) by their distance to a fixed vertex. This is a distance partition. This works because the J(n, k) is a distance-regular graph.

Example 7

Let X_1 be the set of k-spaces in J_q(n, k) containing a fixed 1-space p and let X_2 be the set of k-spaces not containing p. Then it is easy to see that we again have an equitable partition. The graph J_q(n, k) is also distance-regular, so we can also choose the distance partition.

Example 8

Let X_1 be the set of permutations of S_n which map a to b and let X_2 be the set of remaining permutations. Again this defines an equitable partition of \overline{D}_n. Here b_{11} = (n-1)(n-2)/2, b_{12} = n-1, b_{21} = 1, and b_{22} = n(n-1)/2-1.

In this case we cannot use the distance partition to obtain all the eigenvalues as the graph \overline{D}_n is not distance regular. If we instead fix a vertex x and partition V(\overline{D}_n) by the conjugacy class of xy^{-1}, then again we obtain an equitable partition.

Association Schemes

I will not define association schemes here (see Chris Godsil’s nice notes on this for more details), but this seems to be the appropriate time to remark that when you can fix any vertex x and partition the remaining vertices y according to their relation to x (by distance or conjugacy class or something similar) and this is an equitable partition, then this is usually an association scheme. This is algebraic structure investigated in many ways by algebraists and and used in many ways by combinatorialists.

Ordering the Eigenspaces

We saw that for J(n, k) we have a natural ordering of the eigenspaces: We already know that the all-ones vector is an eigenvector, so this is our trivial eigenspaces V_0. If we take the equitable partition induced by partitioning V(J(n, k)) into everything containing a fixed element p and everything not containing p, then we obtain a second eigenvalue with its corresponding eigenspace V_1. Let p^+ denote the indicator vector of p \in \{ 1, \ldots, n \}, that is (p^+)_x is 1 if p \in x and 0 otherwise. Indeed, V_0+V_1 is spanned by \{ p^+: p \in \{ 1, \ldots, n \}\}. Next V_0+V_1+V_2 is spanned by the indicator vector of pairs of elements \ell, V_0+V_1+V_2+V_3 by triples and so on.

The graph J_q(n, k) behaves in a very similar way, just that p is a 1-space, \ell a 2-space and so on: the eigenspaces V_0 + V_1 + \ldots + V_t are spanned by the indicator vectors of t-spaces. This is a general property for many highly symmetric graphs such as distance-regular graphs.

This no longer works for \overline{D}_n for various reasons, but it is still natural to denote the non-trivial eigenspace corresponding to the equitable partition in Example 8 by V_1 (or by some union of eigenspaces if it yields a partition into more parts). And there is a standard way of obtaining a partial ordering of the eigenspaces, starting with V_1, but I that will not concern us too much.

The Strength and Covering Radius of a Set

Let \mathcal{F} be a subset of vertices our graph X with some natural partial ordering of eigenspaces. For simplicity assume that X is distance regular and has a proper ordering of eigenspaces V_0 + V_1 + V_2 + \ldots + V_k (a so-called Q-polynomial association scheme). We write f for the characteristic vector of \mathcal{F}, so f_x = 1 if x \in \mathcal{F} and f_x = 0 otherwise. Clearly, we can write f as a sum of eigenvectors f = v_0 + v_1 + \ldots + v_k, maybe some of these equal to 0. The strength of \mathcal{F} is the largest s such that v_i = 0 for all i \in \{ 1, \ldots, s \} (with s = 0 if v_1 \neq 0). The set \mathcal{F} is a completely regular if it is an equitable partition. The covering radius of \mathcal{F} is the number of non-trivial eigenvalues in the equitable partition.

We limit ourselves to distance-regular graphs which makes things easier. For example for \overline{D}_n all these definition would be slightly more complicated (that is why I am not presenting them).

Example 9

Our Example 4 has has strength 0 and covering radius 1. Our Example 5 has strength 0 and covering radius 2.

Example 10

It is well-known that a perfect code of J(n, k) is an example for a completely regular set. In fact, Delsarte defined the notion of completely regular as a generalization of perfect codes. Perfect codes are very rare, for example there are only three perfect codes in J(n, k). See Natalia Silberstein’s Master thesis for a nice argument for this.

Analysis of Boolean Functions

Up to now, we mostly thought of our set \mathcal{F} as a vector f with entries 0 and 1. Alternatively, we can think of f as a function from V(X) to \{ 0, 1 \}. That is a Boolean function. Traditionally, the term Analysis of Boolean Functions is only used if one works in the hypercube, so V(X) = \{ 0, 1 \}^n, but in the last years there is some interest in transferring results to other highly symmetric association schemes (our introduction here provides a few references).

Warning: We think about the reals. In some areas of Boolean analysis — in particular bent functions — one works over the binary field.

Again, Degree and Eigenspaces

Recall that in J(n, k) the Boolean function p^+ is defined by p^+(x) = 1 if and only if p \in x. Then we can write any function f: V(J(n, k)) \rightarrow \mathbb{R} as a polynomial in the variables p^+. In other words, we have f = c + \sum_p c_p p^+ + \sum_{p_1, p_2} c_{p_1, p_2} p_1^+ p_2^+ + \ldots. Now we can ask for all the Boolean functions of degree 1. So we have f = c + \sum_p c_p p^+ and the image of f is in \{ 0, 1 \}. But recall that above we learned that the p^+ span V_0 + V_1. Hence, Boolean degree 1 functions are just 0-1 vectors in the subspace V_0 + V_1.

Whenever we have some form of lattice where something can take a role similar to the elements of \{ 1, \ldots, n \}, we can define Boolean degree t functions (or more, generally, degree s functions) in similar way. For J_q(n, k) these are the 1-spaces. For \overline{D}_n these are all the maps from a to b.

When using linear algebra methods, then one often investigates the decomposition of f into eigenvectors, that is f = v_0 + v_1 + \ldots + v_k as above. In the analysis of Boolean functions it is common denote this as Fourier transform of f.

Different points of view are always helpful for approaching a research problem. In the following two examples for this.

Example 11

Consider the hypercube, that is the graph of all subsets of \{ 1, \ldots, n \}. What are the Boolean degree 1 functions? Just 0, 1, p^+, 1-p^+. Seen as a degree 1 polynomial this is an easy exercise. Seen more generically as a 0-1 vector in V_0 + V_1, this is slightly harder to see.

Example 12

Now what non-trivial properties has Boolean degree 1 function f on J_q(4, 2). A very straightforward linear algebra argument shows you that q^2+q+1 divides the size of f. When just writing f as a degree 1 polynomial I do not know how to see this easily — except of course by emulating the linear algebra argument.

Warning: Boolean degree 1 functions are not a strict subset of equitable partitions. It can be that the p^+ span more than one eigenspace. Also if the characteristic vector of a set lies in more than one non-trivial eigenspace, then there is no guarantee that it is an equitable partition.

Permutation Groups and Cameron-Liebler sets

Next let us explain the word Cameron-Liebler line class. Consider again S_n canonically acting on \{ 1, \ldots, n \}. Any subgroup H of S_n partitions the set of k-sets on \{ 1, \ldots, n \} into orbits. In particular, we have some number A of orbits on 1-sets and some number B of orbits on 2-sets. It is easy to see that A \leq B. But when do we have equality? It turns out that there are only two cases: either H = S_n with A = B = 1 or H is the stabiliser of a 1-set and A = B = 2. You might realize that the second example is the equitable partition from Example 4. That describes a Boolean degree 1 function. Hence, asking for equality asks for Boolean degree 1 function which are induced by subgroups of S_n.

In 1982 Cameron and Liebler asked the same question for J_q(n, k). Here A is the number of orbits of the projective general linear group PGL(n, q) on 1-spaces and B the number of orbits on 2-spaces. Again, when do we have equality in A \leq B? There are a few obvious examples and Cameron and Liebler conjectured that these are all examples (more on this in the announced future post). Again, any example corresponds to a Boolean degree 1 function. There are surprisingly many non-obvious example for Boolean degree 1 functions and in the research in finite geometry around this topic, the term Cameron-Liebler line class (or some variation of it) is well-established.

Tactical Decompositions

In general, taking subgroup of a collineation group of graph is a natural way of obtaining equitable partitions. The keyword here is tactical decomposition (of (sub)group orbits). The process is very straightforward: suppose that you have a vertex transitive graph G with automorphism group Aut(G). Take any subgroup H of Aut(G). Then the orbits of H on vertices define an equitable partition. This is a natural of way looking for example for equitable partitions with special described properties. Indeed, the many known examples for non-trivial Boolean degree 1 functions in J_q(n, k) were found by combining unions of orbits for a suitable subgroup H. This is called finding a tactical decomposition. There are many nice text on tactical decompositions, for instance this one by Anton and Dieter Betten.

Design Orthogonality

For the sake of completeness, I want to mention that sometimes all the objects above are defined by using design orthogonality. To my knowledge this concept goes (again!) back to Delsarte. This definition is very specialized. For example for J(n, k), n a multiple of k, and n/k \geq 3, it goes as follows: Let g be the characteristic functions of \{ 1, \ldots, n \} into k-sets. A (Boolean) function f has degree 1 if and only if it meets g^h in a constant number of elements (for h being an element of S_n acting canonically).

Example 13

Let \mathcal{F} be the family of all vertices of J(n, k) which contain 1. If k divides n, then each partition of \{ 1, \ldots, n \}[ contains exactly one element of \mathcal{F}.

Finite Geometry: Tight Sets, Intriguing Sets, m-Ovoids …

Cameron-Liebler line class is not the only word for the same object in finite geometry. The collinearity graph G of a finite classical polar space or a generalized quadrangle is strongly regular which implies that the adjacency matrix has only three eigenspace, so we can decompose as V_0 + V_1 + V_2. A coclique of G which satisfies the ratio bound (also called Hoffman’s bound) with equality (this is my obligatory reference to my WordPress username) lies in V_0 + V_2 (notice that is is debatable what the natural ordering of the eigenspaces is). This is an equitable partition and an equitable partition in V_0 + V_2 is usually called m-ovoid. Similarly, an equitable partition in V_0 + V_1 is called x-tight set. The general umbrella term for an equitable partition is intriguing set. De Bruyn and Suzuki define an intriguing set more generally as an equitable partition with two parts for any regular graph, so any 0-1 vector in V_0 + V_i.

Some Concluding Words

Originally, I planned on just writing a blog post about my paper with Yuval. Then I met Dirk Frettloh during Kolkom 2018 recently. He gave a talk on equitable partitions for some small graphs. There I claimed to him that my article mentions some of the words which are used in specific settings to describe equitable partitions. Sadly, I realized still during the conference (looking at our article again) that we did not even mention the word equitable partition. This blog post is aimed at amending this situation. Also I am sure that many of the things above were rediscovered and investigated independently a few more times.

It is (at least for me) exhausting to cover all these terms and translate them correctly. I apologize for any imprecision. Please let me know in the comments. This is a blog post, so that I can easily fix things.

Acknowledgements: I thank John Bamberg for suggesting that I add the term “tactical decomposition”. Also thanks to Karen Meagher for pointing out that Example 3 is the transposition graph.

Advertisements

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.

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.