Schrijver’s SDP Bound for Network Codes

This is a small report on a failed project — obtaining semidefinite programming bounds on constant dimension network codes. But let us start with some context …

A network code consists of a set of subspaces in \mathbb{F}_q^n. It is a code, so we want to maximize the distance between subspaces (or increase the code’s cardinality or rate). The most reasonable metric for this is the subspace metric in which two subspaces U and W have distance \dim(U+W) - \dim(U \cap W), that is the shortest distance between U and W in the subspace lattice. These codes are used in random linear network coding, that is a method for the many-to-many transmission of data in a network which is faster than multiple one-to-one connections. As in classical coding theory, one area of research on those subspace codes is concerned with bounding the maximal size of a code with minimum distance d in \mathbb{F}_q^n. Notice that one can interpret q=1 as a field with one element as is explained here by Peter Cameron. Then it corresponds to classical coding theory.

One method for bounding codes is Delsarte’s linear programming (LP) bound. Delsarte noticed in his PhD thesis (written in 1973) that one can very efficiently calculate Lovász’ theta function (only defined later in 1979) in so-called association schemes, where it corresponds to a very small linear program. Classical coding theory works on subsets of \{ 1, \ldots, n \}, which is an association scheme. This makes it possible to calculate the LP bound very efficiently for relatively large n and d. If we go from coding theory to network coding theory, then we go from subsets of \{ 1, \ldots, n \} to subspaces of \mathbb{F}_q^n. This is no longer an association scheme, but a coherent configuration and in coherent configurations Lovász’ theta function corresponds to a small semidefinite program (SDP). Sylvia Hobart and Jason Williford described this nicely in Delsarte’s style of notation.

These SDP bounds for network codes were first calculated by Bachoc, Passuello and Vallentin for small n, q=2 or d odd. Now a few months ago I met Daniel Heinlein at the conference Combinatorics 2018 in Arco, Italy, and he told me that he would like to update the results by Bachoc et al. One reason for this is that they did not cover q > 2 and d even. Another reason is that since their paper was published, many better bounds on codes on k-spaces of \mathbb{F}_q^n were obtained. Daniel wanted to add these additional constraints, coming from bounds on constant dimension codes, to the SDP and obtain better bounds. Indeed, this worked out very well. We now have a paper on the arXiv and we are now the record holders for many upper bounds. You can find the best known bounds for subspace codes under, a website primarily maintained by Daniel.

So this was a successful project. Where is the failed project?

Schrijver noticed based on previous work of him together with Lovász, that Delsarte’s LP bound for codes can be improved if we refine the optimization problem by fixing one code word c and considering all the other code words in relation to c. For constant weight codes Schrijver used this to obtain many new bounds and for the following I will call this type of bound Schrijver’s SDP bound. For example if we look at codes of length 17, weight 7 and minimum distance 6, then Delsarte’s LP bound gives an upper bound of 249, other techniques at the time of Schrijver’s paper gave 234, Schrijver’s SDP bound improved this to 228, and, extending Schrijver’s method, the current best is due to Polak with 206 from last year. It is worth mentioning that Schrijver needed the so-called Terwilliger algebra/centralizer algebra of the corresponding graph to calculate some of the semidefinite matrices for the SDP.

So this is promising! Let us do the same for network codes, for instance for 7-dimensional spaces in \mathbb{F}_2^{17} and minimum distance 6. This is where the problems started. As far as I could tell, this the centralizer algebra for vector spaces was not known in sufficient detail, so Maarten de Boeck, a colleague of mine and fellow postdoc at Ghent University, and I started calculating it. But then I went to a research stay to the Tohoku University, Sendai, Japan. There I talk to my host, Hajime Tanaka, and he tells me that a former student of his, Yuta Watanabe, already did all of this in his Master thesis! Indeed, the centralizer algebra for vector spaces was calculated in disguise by Dunkl in 1978 and Watanabe explains this nicely in his thesis (which does not seem to be online, so I can only give you my word for it).

Now we are all set and can run an SDP solver! But what happens? Delsarte’s LP bound and Schrijver’s SDP bound turn out to be the same for all the tested parameters. Failure!

Of course I wanted to rule out any errors on my part, so I used the fact that Dunkl’s formulas work for all q > 1, not just prime powers. If I did everything correctly, then Schrijver’s SDP should approach the value 228 in Schrijver’s paper for q \rightarrow 1 as q=1 corresponds to the classical case. This actually happens:

q LP SDP Difference
2 1450279444830258 1450279444830258 0
1.1 4627 4627 0
1.09 3445 3445 0
1.08 2574 2548 26
1.07 1931 1882 49
1.06 1455 1388 67
1.05 1101 1020 81
1.04 831 746 85
1.03 605 547 58
1.02 445 405 40
1.01 331 303 28
1.001 256 235 21
1.0001 250 229 21
1.00001 249 229 20
1 249 228 21

Therefore, I did (most likely) everything correctly and the Schrijver’s SDP is just not better than Delsarte’s LP bound for network codes — at least for the small parameters which I tested, but even 1450279444830258 is already quite gigantic. This concludes my report on this failed project.

What is the outlook? Using higher moments such as Polak for his bound of 206 might help (see Section 4.3 here). But here we have no centralizer algebra to use, so I am not sure if any calculations are currently feasible.

Acknowledgements: I thank Daniel Heinlein and Hajime Tanaka for their comments on a draft of this document.

Bonus Question: The field with one element has its own Wikipedia article. But what is a field with 1.01 elements?


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.

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:


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:


  • \{ \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:


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.


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.