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:

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

For each simplex A in $\mathcal{F}$ there is a simplex B in $\mathcal{F}$ which is opposite to A in $\Delta$ .
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$ .

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 $\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.

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$ .
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.

One comment

Pingback: Bielefeld Buildings Conspiracy | Ratio Bound – A Combinatorics Blog

	igorpak on How to Phrase/Make a Conj…
	Bielefeld Buildings… on Erdős-Ko-Rado Theorems for Sph…
	Collecting Strongly… on Constructing Cospectral Graphs
	Collecting Strongly… on Sp(6, 2)’s Family, Plots…
	Ferdinand Ihringer on Constructing Cospectral Graphs

Ratio Bound – A Combinatorics Blog

Erdős-Ko-Rado Theorems for Spherical Buildings

EKR Theorems

Spherical Buildings

What is known?

Vector Spaces: Type A_n

“Normal” Polar Spaces: Type B_n/C_n

Hyperbolic Polar Spaces: Type D_n

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

Techniques

High-Dimensional Combinatorics

One comment

Leave a Reply Cancel reply

EKR Theorems

Spherical Buildings

What is known?

Vector Spaces: Type A_n

“Normal” Polar Spaces: Type B_n/C_n

Hyperbolic Polar Spaces: Type D_n

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

Techniques

High-Dimensional Combinatorics

Share this:

Like this:

Related

One comment

Leave a Reply Cancel reply