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 . A family of pairwise intersecting k-sets of satisfies . If equality holds and , then is the family of all sets that contain one given element.

For 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 and we denote the number of k-spaces in by .

**EKR Theorem for vector spaces: **Let . A family of pairwise intersecting k-spaces of the n-dimensional vector space over the field with q elements satisfies .

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:

- is the family of all k-spaces that contain one given 1-space.
- and is the family of all k-spaces that are contained in one given -space.

Unlike in the set case, here a characterization of the 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 is a spherical building of type with this diagram: O–O–O. Here we have the following objects:

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

The important thing here are *maximal flags*, that is a set of subspaces with and (so one of each the three dots). Now we can define a graph with all maximal flags as vertices and two vertices and are adjacent if we only have to change one subspace to turn into .

**Examples: **(here is the standard basis of )

- and adjacent.
- and adjacent.
- and are not adjacent, but at distance 2 ( is adjacent to both).
- and are at distance 3. Here is one path between these two flags: , , , .
- and 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 , 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: **

- and are adjacent because the 2-spaces intersect in , but also — when we fill in the *’s — we see that the maximal flags that contain and 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. and .
- and 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 and .

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 of pairwise non-opposite vertices in the graphs of flags of type { 2 } in ?

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 such vertices and in the case of equality one of the following occurs:

- is the family of all 2-spaces containing a fixed 1-space .
- is the family of all 2-spaces in a fixed 3-space .

Let us assume that the first case occurs. Let be another 1-space. Then (using a reasonable definition of distance) one can see that W is never closer to a member of than U. This means that is a center of 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 of a spherical building (read: convex set of vertices in the graph of maximal flags) satisfies one of the following:

- For each simplex A in there is a simplex B in which is opposite to A in .
- The group fixes a non-trivial subcomplex of , that is 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 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 we have flags of type , for 2-spaces we have , and if we only take pairs of incident 1- and 3-spaces, then we have . Klaus Metsch, Bernhard Mühlherr, and I recently defined the EKR problem in this setting as follows:

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

- What is the largest size b of a family of flags of type J which are pairwise non-opposite?
- 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 , that are buildings of type with flags of type . 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 due to Hsieh. The center is a flag of type { 1 }.
- Flags of type { k } for 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 due to Blokhuis and Brouwer. (Diagram with 2 and 3 big: o–O–O–o)
- Flags of type { 1, 3 } for 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.

- Take all flags ( A, B ) (of type { 2, 3 }) with together with one of the following: (a) all flags (A, B) with and or (b) all flags (A, B) with and .
- Take all flags ( A, B ) (of type { 2, 3 }) with together with one of the following: (a) all flags (A, B) with and or (b) all flags (A, B) with and .

**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, , 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 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. Here is the diagram of D_6:

One can embed this geometry in the vector space 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 be a r-regular graph on v vertices and smallest eigenvalue (of the adjacency matrix of ). Then an independent set in has at most size .

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.

## One comment