Buildings and s-Transitive Graphs

Abstract

A graph is s-transitive if its automorphism group acts transitively on the set of paths of length s. This is a notion due to William Tutte who showed in 1947 that a finite trivalent graph can never be 6-transitive. We examine connections between the theory of s-transitive graphs and the classification of Moufang polygons, a class of graphs exhibiting “local” s-transitivity for large values of s. Moufang polygons are examples of buildings. Both of these notions were introduced by Jacques Tits in the study of algebraic groups. We give an overview of Tits’ classification results in the theory of spherical buildings (which include the classification of Moufang polygons as a special case) and describe, in particular, the classification of finite buildings.

1 Introduction

Jacques Tits’ classification of spherical buildings [8], published in 1974, is one of the great accomplishments in group theory. Starting with only a Coxeter group and a few combinatorial/geometrical axioms, he succeeded with this result in characterizing a large class of simple groups which includes, as a special case, all the finite simple groups of Lie type of rank at least 3.

In subsequent work (mainly [10] and [12]), it emerged that Tits’ theory of spherical buildings can be described purely in terms of graph theory and that there are great advantages in taking this point of view. In these notes, we describe the main steps in the classification of spherical buildings in the language of graph theory and highlight a connection to the theory of s-transitive graphs which had been introduced earlier by W. T. Tutte in [13].

2 s-Transitive Graphs

A graph Γ is called s-transitive if its automorphism group acts transitively on the set of paths of length s in Γ but intransitively on the set of paths of length s + 1 (in which case the valency of Γ must be greater than 2). The notion of an s-transitive graph was introduced and developed by Tutte in [13] and [14]. If a graph Γ is s-transitive and has girth γ (i.e. γ is the length of a shortest circuit in Γ), then

$$\displaystyle{\gamma \geq 2s - 2.}$$

Tutte defined a γ-cage to be a connected s-transitive graph of girth γ such that either $\gamma = 2s - 2$ or $\gamma = 2s - 1$. If Γ is a γ-cage, then the diameter n of Γ is s − 1 and if γ is even, then

$$\displaystyle{ \mbox{ $\varGamma $ is bipartite and $\gamma = 2n$.} }$$

(1)

A complete graph on a set X is a 3-cage if | X |  > 3 and the complete bipartite graph on a pair of sets X and Y is a 4-cage as long as | X |  =  | Y |  > 2. The Petersen graph is a 5-cage.

Let V be a 3-dimensional right vector space over a field or skew-field K, let X be the set of 1-dimensional subspaces of V, let Y be the set of 2-dimensional subspaces of V and let E be the set of pairs {x, y} such that x ∈ X, y ∈ Y and x ⊂ y. The graph with vertex set X ∪ Y and edge set E is a 6-cage. It is also the incidence graph of the projective plane associated with V. If | K |  = 2, this graph is called the Heawood graph.

Let W = { 1, 2, 3, 4, 5, 6}, let X be the set of all 2-element subsets of W, let Y be the set of partitions $u/v/w$ of W into three blocks u, v and w of size 2 and let E be the set of pairs $\{x,u/v/w\}$ such that x ∈ X, $u/v/w \in Y$ and x ∈ { u, v, w}. The graph with vertex set X ∪ Y and edge set E is an 8-cage. This graph is often called Tutte’s 8-cage.

Tutte showed in [13] that the only trivalent cages are the complete graph, the complete bipartite graph, the Petersen graph, the Heawood graph and his 8-cage. In fact, his proof showed much more (see [6]):

Theorem 1.

Let Γ be an arbitrary connected trivalent graph—even a tree—and let u be a vertex of Γ. Suppose that G is a group acting transitively on paths of length s in Γ for some s ≥ 1 but not on paths of length s + 1 and that the stabilizer G _u is finite. Then s ≤ 5 and for each value of s, the structure of G _u is uniquely determined.

This was a result of great originality and, in some sense, far ahead of its time. It has been generalized in a number of directions. One generalization (proved in [16] and [18]) is the following:

Theorem 2.

Let Γ be an arbitrary connected graph and let u be a vertex of Γ. Suppose that G is a group acting transitively on paths of length s in Γ for some s ≥ 4 but not on paths of length s + 1 and that the stabilizer G _u is finite. Then s = 4, 5 or 7 and for each value of s, the structure of G _u is uniquely determined in an appropriate sense.

An important ingredient in the proof of Theorem 2 is the Theorem of Thompson-Wielandt. Here is the relevant version of this result; see [4] or [15] for a proof.

Theorem 3.

Let Γ be an arbitrary connected graph and let {u,v} be an edge of Γ. Suppose that G is a group acting transitively on the vertex set of Γ and that the stabilizer G _u is finite and acts primitively on Γ _u , the set of neighbors of u in Γ. Then $\vert G_{u,v}^{[1]}\vert$ is divisible by at most one prime, where $G_{u,v}^{[1]}$ denotes the pointwise stabilizer in G of Γ _u ∪Γ _v .

Here now is how the proof of Theorem 2 begins. Let {u, v} be an edge of Γ. Replacing G by the free amalgamated product $G_{u} {\ast}_{G_{u,v}}G_{v}$, we can assume without loss of generality that Γ is a tree. Let H denote the permutation group induced by G _u on Γ _u . The hypotheses of Theorem 2 imply that the group H acts 2-transitively and hence primitively on Γ _u . It can also be deduced from the hypotheses that the subgroup $G_{u,v}^{[1]}$ is non-trivial. By Theorem 3, therefore, there is a unique prime p dividing the order of this subgroup. It follows from this that the stabilizer H _v of a vertex v ∈ Γ _u has a non-trivial normal subgroup of order a power of p. At this point the classification of finite 2-transitive groups (which rests on the classification of finite simple groups) is invoked. From this it can be deduced that H contains a normal subgroup isomorphic to the group PSL ₂(q) in its natural action on $\vert \varGamma _{u}\vert = q + 1$ points. This is the conclusion reached in [18].

With this conclusion as an hypothesis, it is shown in [16] (see also [2, 3.6]) that there is a G-compatible local isomorphism $\varphi$ from the tree Γ to a 2(s − 1)-cage $\hat{\varGamma }$. By ‘local isomorphism’ we mean that $\varphi$ is a map from the vertex set of Γ to the vertex set of $\hat{\varGamma }$ such that if $\varphi (x) =\hat{ x}$, then $\varphi$ induces a bijection from Γ _x to $\hat{\varGamma }_{\hat{x}}$, and by ‘G-compatible’ we mean that if $\varphi (x) =\varphi (y)$, then $\varphi (x^{g}) =\varphi (y^{g})$ for all g ∈ G. It follows that G induces a group of automorphisms $\hat{G}$ of $\hat{\varGamma }$ and that if $\hat{u} =\varphi (u)$, then $\varphi$ induces an isomorphism from the stabilizer G _u to the stabilizer $\hat{G}_{\hat{u}}$. At this point, the proof is concluded by citing the classification of 2(s − 1)-cages. This is a special case of the classification of Moufang polygons which we describe in the next section.

3 Moufang Polygons

The following notion was introduced by Tits in [7].

Definition 1.

A generalized n-gon is a bipartite graph Γ with diameter n ≥ 2 and girth γ such that

$$\displaystyle{\gamma = 2n.}$$

A generalized polygon is a generalized n-gon for some n ≥ 2. A generalized triangle, quadrangle, etc., is a generalized n-gon for n = 3, n = 4, etc.

By (1), a γ-cage for γ even is automatically a generalized n-gon for $n =\gamma /2$. Note, however, that there is no group in the definition of a generalized polygon.

We say that a graph Γ is thick if | Γ _u  | ≥ 3 for all vertices u, respectively, Γ is thin if | Γ _u  |  = 2, for all vertices u (so many graphs are neither thick nor thin).

Let Γ be a generalized n-gon for some n ≥ 2. Since Γ is bipartite, it can be regarded as the incidence graph of a geometry $\mathcal{G}$ consisting of points X and lines Y. If Γ is thin, the geometry $\mathcal{G}$ is just the set of points and lines of an ordinary n-gon, hence the name generalized n-gon.

Suppose that n = 2 and choose x ∈ X and y ∈ Y. Then the distance from x to y in Γ is odd because Γ is bipartite. Since the diameter of Γ is 2, it follows that x and y are adjacent in Γ. We conclude that Γ is a complete bipartite graph.

Suppose that n = 3 and choose distinct vertices x, y both in X. Then the distance from x to y is even and bounded by the diameter 3 of Γ. Hence there is a vertex z ∈ Y adjacent to both x and y. Since the girth of Γ is 2n = 6, the vertex z is unique. Thus any two points of the geometry $\mathcal{G}$ are incident with a unique line. By a similar argument, any two lines of $\mathcal{G}$ are incident with a unique point. We conclude that Γ is the incidence graph of a projective plane. Conversely, the incidence graph of an arbitrary projective plane is a thick generalized triangle. Thus a generalized triangle is essentially the same thing as a projective plane.

This means, in particular, that there is no hope of classifying generalized polygons. In the appendix of [8], however, Tits introduced the notion of a Moufang polygon and asked whether it might be possible to classify them.

Definition 2.

A root of a generalized n-gon Γ is a path of length n. To each root $\alpha = (x_{0},x_{1},\ldots,x_{n})$, there is a corresponding root group U _α , the pointwise stabilizer of $\varGamma _{x_{1}} \cup \cdots \cup \varGamma _{x_{n-1}}$ in G: = Aut(Γ). Thus

$$\displaystyle{U_{\alpha } = G_{x_{1},\ldots,x_{n-1}}^{[1]}.}$$

A generalized n-gon Γ is said to satisfy the Moufang condition if it is thick, n ≥ 3 and for each root $\alpha = (x_{0},x_{1},\ldots,x_{n})$ in Γ, the corresponding root group U _α acts transitively on $\varGamma _{x_{n}}\setminus \{x_{n-1}\}$. A Moufang polygon is a generalized polygon that satisfies the Moufang condition.

Moufang triangles, in the guise of Moufang projective planes, were first studied by Ruth Moufang in the 1930s, hence the name Moufang.

The automorphism group of a Moufang n-gon Γ does not necessarily act transitively on the vertex set of Γ. If it does, however, then Γ is automatically (n + 1)-transitive. It follows that a Moufang n-gon is a 2n-cage if and only if its automorphism group acts transitively on the vertex set of Γ. The 2(s − 1)-cage $\hat{\varGamma }$ at the end of the previous section is, in fact, a Moufang n-gon with $n = s - 1$, and a more accurate statement of Theorem 2 (as proved in [16] and [18]) is as follows:

Theorem 4.

Let Γ be a thick tree and let u be a vertex of Γ. Suppose that G is a group acting transitively on paths of length s in Γ for some s ≥ 4 but not on paths of length s + 1 and that the stabilizer G _u is finite. Then there exists a Moufang (s − 1)-gon $\hat{\varGamma }$ , a G-compatible local isomorphism $\varphi$ from Γ to $\hat{\varGamma }$ and a subgroup $\hat{G}$ of $\mathrm{Aut}(\hat{\varGamma })$ containing all the root groups of $\hat{\varGamma }$ such that $G_{u}\mathop{\cong}\hat{G}_{\varphi (u)}$ for all vertices u of Γ.

Corollary 1.

Let Γ be a 2n-cage for some n ≥ 2. Then either n = 2 and Γ is a complete bipartite graph or n ≥ 3 and Γ is a Moufang n-gon.

The classification of Moufang polygons was carried out in [12]. We use the rest of this section to sketch how this classification works. The first step is the following result [9]:

Theorem 5.

Moufang n-gons exist only for n = 3, 4, 6 and 8.

It was shown in [17] that, in fact, the following holds:

Theorem 6.

Let n ≥ 3, let Γ be a thick graph and let G be a subgroup of Aut (Γ) such that

• 1. $G_{x_{1},\ldots,x_{n-1}}^{[1]}$ acts transitively on $\varGamma _{x_{n}}\setminus \{x_{n-1}\}$ and

• 2. $G_{x_{0},x_{1}}^{[1]} \cap G_{x_{0},\ldots,x_{n}} = 1$

for all paths $(x_{0},x_{1},\ldots,x_{n})$ of length n in Γ. Then n = 3, 4, 6 and 8.

It is easy to see that condition (2) in Theorem 6 holds automatically if Γ is a generalized n-gon. Thus Theorem 5 is a corollary of Theorem 6. If Γ, G and s are as in Theorem 1 and s ≥ 4, then the hypotheses of Theorem 6 hold with $n = s - 1$. In contrast to Theorem 2, the proof of Theorem 6 does not depend on the classification of finite simple groups (or on anything else, for that matter). Note, too, that it is not assumed in Theorems 5 and 6 that the stabilizers are finite.

The next step in the classification of Moufang polygons is to choose a circuit Σ of length 2n in a Moufang n-gon Γ and label its vertices by integers modulo 2n. We then let α _i denote the root $(i,i + 1,\ldots,i + n)$ and let U _i denote the root group $U_{\alpha _{i}}$ as defined in Definition 2 for all i. We set

$$\displaystyle{U_{[i,j]} =\langle U_{i},U_{i+1},\ldots,U_{j}\rangle }$$

for all i, j such that i ≤ j and U _[i, j] = 1 if j < i. Let W = U _[1, n]. By [12, 4.11 and 5.3], the group W acts regularly on the set of circuits of length 2n containing the edge {n, n + 1}. Since every two edges of Γ are contained in a circuit of length 2n, it follows that every vertex of Γ is in the W-orbit of a unique vertex of Σ and every edge of Γ is in the W-orbit of a unique edge of Σ. By [12, 7.3], the stabilizers in W of the vertices 1, …, n of Σ are

$$\displaystyle{U_{1},U_{[1,2]},\ldots,U_{[1,n]}}$$

and the stabilizers in W of the vertices n + 1, …, 2n are

$$\displaystyle{U_{[1,n]},U_{[2,n]},\ldots,U_{n}.}$$

It follows from these observations that the graph Γ can be reconstructed from the cosets of these subgroups in W and hence that Γ can be reconstructed from the (n + 1)-tuple

$$\displaystyle{\varOmega = (W,U_{1},\ldots,U_{n}).}$$

See [12, 7.5] for the details. We call the (n + 1)-tuple Ω a root group sequence of Γ. It depends on the choice of Σ and its labeling, but it is independent of these choices up to conjugation and opposites. The opposite of the root group sequence Ω is the root group sequence

$$\displaystyle{(W,U_{n},\ldots,U_{1}).}$$

Every element of W can be written uniquely as a product $a_{1}a_{2}\cdots a_{n}$ with a _i  ∈ U _i for all i ∈ [1, n]. Another crucial observation is that

$$\displaystyle{ [U_{i},U_{j}] \subset U_{[i+1,j-1]} }$$

(2)

for all i, j such that 1 ≤ i < j ≤ n, where [U _i , U _j ] denotes the subgroup generated by the commutators $[a,b] = a^{-1}b^{-1}ab$ for all a ∈ U _i and all b ∈ U _j . (Thus, in particular,

$$\displaystyle{ [U_{i},U_{i+1}] = 1 }$$

(3)

for all i such that 1 ≤ i < n.) The commutator relations (2) determine the structure of W uniquely. We conclude that to describe the root group sequence Ω and thus the graph Γ, it suffices to give the structure of the individual root groups U ₁, …, U _n and the commutator relations (2). In each case, these things are given in terms of certain algebraic data.

Suppose first that n = 3. In this case the classification of Moufang polygons tells us that there is an invariant K of Γ that is either a field, a skew-field or an octonion division algebra and there exist isomorphisms x _i from the additive group of K to U _i for i = 1, 2 and 3 such that

$$\displaystyle{[x_{1}(s),x_{3}(t)] = x_{2}(st)}$$

for all s, t ∈ K. By (3), the root group sequence Ω and hence the generalized triangle Γ are uniquely determined by K. (See [12, 9.3–9.4 and 9.11] for the definitions of quaternion and octonion division algebras.)

There are six different families of Moufang quadrangles. In the first, there is a triple (K, L, q), where K is a field, L is a vector space over K and q is an anisotropic quadratic form on L, as well as isomorphisms x _i from the additive group of K to U _i for i = 1 and 3 and isomorphisms x _i from the additive group of L to U _i for i = 2 and 4 such that [U ₁, U ₃] = 1,

$$\displaystyle{ [x_{1}(s),x_{4}(v)^{-1}] = x_{ 2}(sv)x_{3}(sq(v)) }$$

(4)

for all s ∈ K and all v ∈ L and

$$\displaystyle{ [x_{2}(u),x_{4}(v)^{-1}] = x_{ 3}(f(u,v)) }$$

(5)

for all u, v ∈ L, where f is the bilinear form associated with q. By (3), Ω and hence Γ are uniquely determined by (K, L, q).

In the second family of Moufang quadrangles, there is a triple (K, K ₀, σ), where K is a skew-field, σ is an involution of K (i.e. an anti-automorphism of order 2) and K ₀ is an additive subgroup of K containing 1 such that $K_{\sigma } \subset K_{0} \subset K^{\sigma }$, where

$$\displaystyle{K_{\sigma } =\{ a + a^{\sigma }\mid a \in K\}}$$

and

$$\displaystyle{K^{\sigma } =\{ a\mid a^{\sigma } = a\},}$$

and $s^{\sigma }K_{0}s \subset K_{0}$ for all s ∈ K as well as isomorphisms x _i from K ₀ to U _i for i = 1 and 3 and isomorphisms x _i from the additive group of K to U _i for i = 2 and 4 such that [U ₁, U ₃] = 1,

$$\displaystyle{[x_{1}(s),x_{4}(t)^{-1}] = x_{ 2}(st)x_{3}(t^{\sigma }st)}$$

for all s ∈ K ₀ and all t ∈ K and

$$\displaystyle{[x_{2}(r),x_{4}(t)^{-1}] = x_{ 3}(r^{\sigma }t + t^{\sigma }r)}$$

for all r, t ∈ K. By (3), Ω and hence Γ are uniquely determined by (K, K ₀, σ). If char(K) ≠ 2, then $a = (a + a^{\sigma })/2$ for all a ∈ K ^σ, so K _σ  = K ^σ, but if char(K) = 2, this is not true.

The algebraic structures for the remaining Moufang quadrangles and the Moufang hexagons and octagons (which, by Theorem 5, is all there is) are more complicated. We refer the reader to Chapter 16 in [12] and all the references there to earlier chapters of [12] for details. The general pattern is, however, the same: In each case, there is a recipe that turns an algebraic structure of a suitable type via commutator relations into a root group sequence Ω from which, in turn, a unique Moufang polygon can be constructed using cosets.

Let Ω = (W, U ₁, …, U _n ) be a root group system of a Moufang polygon Γ. Then G = Aut(Γ) acts transitively on the vertex set of Γ and hence Γ is a 2n-cage if and only if there is an automorphism $\varphi$ of W such that $U_{i}^{\varphi } = U_{n+1-i}$ for each i ∈ [1, n], i.e. if and only if Ω is isomorphic to its opposite. If n = 3 and K is the invariant of Γ described above, then Γ is a 6-cage if and only if K is isomorphic to its opposite. In particular, Γ is always a 6-cage if K is a field or an octonion division algebra (which always has involutions). If Γ is the Moufang quadrangle determined by an anisotropic quadratic space (K, L, q), then Γ is an 8-cage non-zero, if the characteristic of K is 2, L = K and q(t) = t ² for each t ∈ K, and if K is the field with two elements, then Γ is, in fact, isomorphic to Tutte’s 8-cage as described in Sect. 2 above. A complete list of Moufang polygons whose root group system is isomorphic to its opposite is given in [12, 37.5]. In particular, we can observe that there exist 6-, 8 and 12-cages but no 16-cages.

Tits discovered the notion of a generalized polygon and the Moufang condition by studying the structure of “absolutely simple” algebraic groups. In particular, every absolutely simple algebraic groups “of relative rank 2” has a Moufang polygon associated to it. Not all Moufang polygons come from absolutely simple algebraic groups, however. For example, a Moufang triangle defined by a skew-field K comes from an absolutely simple algebraic group if and only if K is finite-dimensional over its center.

An important notion in the theory of buildings is that of a (B, N)-pair. By the results in Chapter 5 of [5], a group G has a spherical (B,N)-pair of rank 2 if and only if

• 1. There is a generalized n-gon Γ for some n ≥ 2 on which G acts; and

• 2. G acts transitively on the set of pairs (Σ, e), where Σ is circuit of length 2n in Γ and e is an edge of Σ.

Given (1), condition (2) holds if and only if for each vertex u of Γ, the group G acts transitively on the set of paths of length n + 1 in Γ beginning at u. In other words, G has a (B, N)-pair of rank 2 if and only if it acts locally (n + 1)-transitively on a generalized n-gon. If Γ is a Moufang polygon and G is a subgroup of Aut(Γ) containing all the root groups of Γ, then condition (2) holds. It does not follow from conditions (1) and (2), however, that Γ is Moufang.

In Sect. 5 we will describe the connection between Moufang polygons and buildings.

4 Coxeter Complexes

Before we can introduce buildings in the next section, we need to say a few things about Coxeter groups.

A Coxeter diagram is a graph Π whose edges are labeled with elements of the set {3, 4, …, ∞}. Let Π be a Coxeter diagram with vertex set S and edge set E and for each edge {i, j} of Π let m _ij be its label. Let m _ij  = 2 for all 2-element subsets {i, j} of V that are not in E, let m _ii  = 1 for all i ∈ S, let R be a collection of symbols r _i , one for each i ∈ S, and let W denote the corresponding Coxeter group

$$\displaystyle{\langle R\mid (r_{i}r_{j})^{m_{ij} } = 1\text{ for all }i,j \in S\rangle.}$$

By [19, Thm. 2.3], the elements of R have order 2 and r _i ≠ r _j if i ≠ j. In particular, we can identify R with its image in W.

Let Σ _Π denote the Cayley graph associated with this data. Thus Σ _Π is the graph whose vertices are the elements of W and whose edges are the 2-element subsets {x, y} of W such that x ⁻¹ y ∈ R. We endow Σ _Π with the edge coloring obtained by assigning to each edge {x, y} of W the color i ∈ S if and only if $x^{-1}y = r_{i}$. Thus S is simultaneously the set of vertices of Π and the set of colors on the edges of Σ _Π . We call Σ _Π the Coxeter complex associated with Π. (Σ _Π is not, in fact, a complex, but it is easy to see that our definition of the Coxeter complex is equivalent to the more traditional notion of the Coxeter complex.)

The edge-colored graphs Σ _Π have many remarkable properties. We mention only one, a proof of which can be found in [19, 3.11]:

Proposition 1.

Let Σ = Σ _Π be a Coxeter complex and let {x,y} be an edge of Σ. Let α be the set of vertices nearer to x than to y in Σ and let β be the set of vertices nearer to y than to x. Then the vertex set W of Σ is partitioned by α and β. A root of Σ is a subset of W of the form α or β for some edge {x,y}.

Suppose, for example, that | S |  = 2 and | W |  < ∞. In this case, W is generated by two elements of order 2 and Σ = Σ _Π is a circuit of length 2n for some n ≥ 2 with two alternating colors on its edges. Let e and f be an opposite pair of edges of Σ. The roots associated with e are the vertex sets of the two connected components of the graph obtained from Σ by deleting e and f (but without deleting any vertices). Note that if Σ is the edge-graph of a 2n-circuit in a generalized 2n-gon, then these two roots are roots in the sense of Definition 2.

A Coxeter diagram Π is called spherical if the corresponding Coxeter complex Σ _Π is finite. Coxeter himself classified spherical Coxeter diagrams. Their connected components are the Coxeter diagrams underlying Dynkin diagrams, all Coxeter diagrams with at most 2 vertices but without the label ∞, plus two more Coxeter diagrams, H ₃ and H ₄. These last two are the Coxeter diagrams obtained from the Coxeter diagrams B ₃ and B ₄ by replacing the unique label 4 by a 5.

5 Spherical Buildings

We fix an arbitrary Coxeter diagram Π and let S and Σ _Π be as in the previous section.

Suppose Δ is an arbitrary graph whose edges are colored by elements of the set S, one color per edge. For each subset J of S, we let Δ _J denote the graph Δ with all edges deleted whose color is not in J (but with no vertices deleted). A J-residue of Δ for some J ⊂ S is a connected component of Δ _J . Thus for each subset J of S and each vertex x of Δ, there is a unique J-residue of Δ containing x. In particular, for a given J, any two J-residues of Δ are disjoint. A residue of Δ is a J-residue for some J ⊂ S.

A path $(u_{0},u_{1},\ldots,u_{m})$ of length m in a graph Γ is called minimal if there is no path of length less than m in Γ from the vertex u ₀ to the vertex u _m . We say that a subset X of the vertex set of a graph Γ is convex in Γ if for every two vertices x, y in X and every minimal path $(u_{0},u_{1},\ldots,u_{m})$ from u ₀ = x to u _m  = y, all the intermediate vertices u ₁, …, u _m−1 also lie in X.

There are several ways to define a building. Given [19, 4.2 and 8.9], it is not difficult to show that the following is equivalent to the definition given in [19, 7.1]:

Definition 3.

A building of type Π (for a given Coxeter diagram Π with vertex set S) is a graph Δ whose edges are colored by elements of the set S satisfying the following properties:

• 1. The {i}-residues of Δ are complete graphs with at least 2 vertices for each i ∈ S.

• 2. Every two vertices of Δ are contained in some subgraph that is isomorphic to Σ _Π (as an edge-colored graph).

• 3. The vertex set of every subgraph isomorphic to Σ _Π is convex in Δ.

The subgraphs of Δ that are isomorphic to Σ _Π are called apartments of Δ. The {i}-residues for some i ∈ S are called panels or i-panels.

Let Δ be a building of type Π. The vertices of Δ are, for historical reasons, called chambers. By condition (1) of Definition 3, J is precisely the set of colors that appear on the edges of an arbitrary J-residue. Thus J is an invariant of a J-residue. The set J is called the type of a J-residue (or of a J-panel) and the cardinality | J | is called the rank of a J-residue. Thus panels are residues of rank 1. It follows from condition (2) in Definition 3 that Δ is connected and hence Δ itself is the only S-residue and its rank is  | S | . If | S |  = 1, then Δ consists of a single panel and thus Δ is just a complete graph with all its edges painted the same color.

Suppose that | S |  = 2 and let n be the label on the one edge of the Coxeter diagram Π if there is an edge; otherwise let n = 2. Suppose first that n < ∞. In this case, an apartment of Δ is a circuit of length 2n whose edges display, alternatingly, the two colors in S. Let Γ be the graph with vertex set the set of panels of Δ, where two panels are adjacent in Γ if and only if they contain a chamber in common. Distinct panels of the same type are disjoint. Therefore Γ is a bipartite graph. Apartments of Δ correspond to circuits of length 2n in Γ. From condition (2) in Definition 3, it follows that the diameter of Γ is at most n and from condition (3), that the girth of Γ is 2n. This is enough to deduce that Γ is a generalized n-gon. This construction is also reversible. In other words, a building of rank 2 with finite apartments is essentially the same thing as a generalized polygon. If the label n equals ∞, on the other hand, then Δ is a tree and the apartments are the connected subgraphs of valency 2.

For an elementary example of a building of arbitrary rank r with finite apartments arising from a vector space of dimension r + 1, see [19, 7.4].

A building Δ is called irreducible if its Coxeter diagram Π is connected. All buildings are direct products of irreducible buildings in an appropriate sense, so it is, for most purposes, sufficient to study irreducible buildings. A building Δ is called thick if all its panels contain at least 3 chambers, thin if all its panels contain exactly 2 chambers. Thus Σ _Π is an example of a thin building of type Σ _Π and, in fact, it is the only thin building of type Σ _Π . A building Δ is called spherical if its diagram Π is spherical. In other words, a spherical building is a building whose apartments are finite.

Every J-residue of a building of type Π (for a given subset J of S) is itself a building. The type of this building is Π _J , where Π _J denotes the subdiagram of Π spanned by J. Thus it makes sense to say whether a residue is irreducible or spherical: A J-residue is irreducible if and only if the diagram Π _J is connected, and a J-residue is spherical if and only if the diagram Π _J is spherical. Thus every residue of a spherical building is spherical, but it is, of course, not true that every residue of an irreducible building is irreducible.

If | J |  = 2, then a J-residue is irreducible if and only if the two elements of J are joined by an edge in Π and a J-residue is spherical if and only if the two elements of J are not joined by an edge labeled ∞.

For each chamber x of Δ, there is a unique irreducible residue of rank 2 containing x corresponding to each edge of Π. We denote by

$$\displaystyle{ \varDelta _{2}(x) }$$

(6)

the subgraph of Δ spanned by the union of the chamber sets of all these irreducible rank 2 residues.

Suppose that | J |  = 2 and that Π _J is spherical. Let n be the label on the unique edge of Π _J if Π _J is connected; if Π _J is not connected, we set n = 2. Then every J-residue is a building of rank 2 and of type Π _J . Hence every J-residue is the building associated with a generalized n-gon, as explained above. In fact, we can simply think of these residues as generalize n-gons.

A root of a building Δ of type Π is the image under an isomorphism from Σ _Π into Δ of a root of Σ _Π as defined in Proposition 1. Thus a root is always contained in an apartment; in fact, roots are contained in many apartments as long as Δ is thick. For each root α of Δ, the root group U _α is the pointwise stabilizer in Aut(Δ) of the set of chambers contained in some panel containing two chambers of α. A building is called Moufang if it is irreducible, thick, spherical and of rank at least 2 and if for each root α, the root group U _α acts transitively on the set of apartments of Δ that contain α. If | S |  = 2, the notion of a root group and the Moufang property coincide with the notions introduced in Sect. 3.

The main result of [8] is a classification of thick, irreducible spherical buildings of rank at least 3. (We have already observed that buildings of rank 2, namely generalized polygons, include all projective planes and are not, therefore, in any reasonable sense classifiable without additional hypotheses.) This classification rests on the following deep result [8, 4.1.2] of Tits:

Theorem 7.

Let Δ and $\hat{\varDelta }$ be two thick irreducible spherical buildings of the same type Π and let x and $\hat{x}$ be chambers of Δ and $\hat{\varDelta }$ . Suppose that $\varphi$ is an isomorphism from Δ ₂ (x) to $\hat{\varDelta }_{2}(\hat{x})$ —as defined in (6) —mapping x to $\hat{x}$ . Then $\varphi$ extends to an isomorphism from Δ to $\hat{\varDelta }$ .

In other words, a building Δ with all the adjectives in Theorem 7 is uniquely determined by the subgraph Δ ₂(x). The following is an important consequence of Theorem 7:

Theorem 8.

Every thick irreducible spherical building of rank n ≥ 3 as well as all the irreducible residues of rank at least 2 of such a building are Moufang.

For a self-contained proof of these remarkable results carried out entirely in the language of graph theory, see [19, 10.2, 11.6 and 11.8].

Theorems 7 and 8 tell us that, given the classification of Moufang polygons, to classify thick irreducible spherical buildings of rank n ≥ 3, it suffices for each spherical Coxeter diagram Π to examine how Moufang polygons, one for each edge of Π, can be assembled to form the subgraph Δ ₂(x) of a building Δ. (Note that two rank 2 residues contained in Δ ₂(x) overlap in a panel if their types have a nonempty intersection, so the various rank 2 residues really do have to be “assembled” to form a viable Δ ₂(x).)

Suppose first that Π is the Coxeter diagram A _n with n ≥ 3. Then all the irreducible rank 2 residues are Moufang triangles. It turns out that they must all be isomorphic to each other, that there is just one way to assemble them into a Δ ₂(x) and that the division ring K defining these triangles must be a field or a skew-field (i.e. not an octonion division algebra). In other words, for each field or skew-field K, there is just one building of type A _n “defined over K.” The situation is even simpler when Π is the one of the diagrams D _n , E ₆, E ₇ or E ₈. In these cases, there is exactly one building of a given type Π for each commutative field K.

Suppose next that Π is the Coxeter diagram B _n (which is the same as the Coxeter diagram C _n ) with n ≥ 3. In this case, there is exactly one irreducible residue R ₁ containing a given chamber x which is a generalized quadrangle and one irreducible rank 2 residue R ₂ containing x and intersecting R ₁ in a panel P. Suppose that R ₁ is isomorphic to the quadrangle defined by an anisotropic quadratic space (K, L, q). It turns out that there is exactly one way to assemble a Δ ₂(x) starting with the root group sequence

$$\displaystyle{ \varOmega = (W,U_{1},U_{2},U_{3},U_{4}) }$$

(7)

determined by (K, L, q) and Eqs. (4) and (5) in its “standard orientation,” in which [U ₁, U ₃] = 1. In the corresponding building, which we denote by B _n (K, L, q), the root groups acting on the panel P are those parametrized by the additive group of K and all the other irreducible rank 2 residues containing the chamber x, including R ₂, are isomorphic to the Moufang triangle defined by K. If, on the other hand, we use Ω ^op rather than Ω to assemble a Δ ₂(x), we obtain as second building of type B _n , which we call C _n (K, L, q), in which the root groups acting on the panel P are those parametrized by the additive group of L, but this second building C _n (K, L, q) exists only when (K, L, q) is in one of the following cases:

• 1. L is a field of characteristic 2, K is a subfield containing L ² and q(x) = x ² for all x ∈ L.

• 2. L = K and q(x) = x ² for all x ∈ L.

• 3. L∕K is a separable quadratic extension and q is the norm of this extension.

• 4. L is a quaternion division algebra with center K and q is the reduced norm of L.

• 5. L is an octonion division algebra with center K and q is the reduced norm of L.

In each of these five cases, all the irreducible rank 2 residues of C _n (K, L, q) containing x other than R ₁, including R ₂, are isomorphic to the Moufang triangle defined by L. Furthermore, case (5) can only occur when n = 3, there is a unique building F ₄(Λ) of type F ₄ for each anisotropic quadratic space Λ = (K, L, q) in one of the cases (1)–(5), the building F ₄(Λ) has residues isomorphic to B ₃(K, L, q) and others isomorphic to C ₃(K, L, q), and these are the only buildings of type F ₄. For some anisotropic quadratic spaces Λ = (K, L, q), the root group sequences Ω and Ω ^op are isomorphic. In these cases, Λ is in case (1) or (2), char(K) = 2 and C _n (Λ) is isomorphic to B _n (Λ). In general, however, B _n (Λ) and C _n (Λ) are different.

There is just one further family of buildings of type B _n for n ≥ 3. The buildings in this family are defined by pseudo-quadratic spaces (possible of dimension m = 0) over a skew-field with involution. This is the family in [20, 30.14(iv)] for m = 0 and [20, 30.14(vii)] for m > 0. See also Chapter 11 of [12].

This completes the list of thick irreducible spherical buildings of rank n ≥ 3. In particular, there are no thick buildings of type H ₃ and H ₄. If there were, then by Theorem 8, there would be residues which are Moufang 5-gons, but by Theorem 5, no such Moufang polygons exist.

When he published [8], Tits still had no proof that thick buildings of type H ₃ or H ₄ do not exist. A short time later, he introduced the Moufang property and showed that there are no Moufang pentagons precisely in order to eliminate these two diagrams. Carrying this out, Tits noticed that he could extend his methods to yield Theorem 5 and it was this success that led him to conjecture that Moufang polygons could, in fact, be classified.

In every case, the relevant algebraic structure is defined in terms of a field or a skew-field or an octonion division algebra K. The ring K is an invariant of the corresponding building Δ. We call it the defining field of Δ, even though it is not always a field. (This does not coincide entirely with the notion of defining field as it is used in the theory of algebraic groups.) See [20, 30.29–30.31] for details. We will refer to the defining field K in Sect. 7.

6 Finite Buildings

Let Δ be a thick irreducible spherical building of rank n ≥ 2 and suppose that Δ is Moufang if n = 2. (By Theorem 8, the Moufang property is automatic if n > 2.) Let G ^† be the subgroup of Aut(Δ) generated by all the root groups of Δ. With only three exceptions, G ^† is a simple group. In the three exceptions, n = 2 and G ^† is isomorphic to PSp₄(2),²​F ₄(2) or G ₂(2).

Now suppose that G is an arbitrary non-abelian simple group. Then the classification of finite simple groups tells us that one of the following holds:

• 1. $G\mathop{\cong}\ \mathrm{PSL}_{2}(q)$, U₃(q), Suz(q) or Ree(q) for some prime power q.

• 2. G is isomorphic to the group G ^† generated by all the root groups for some finite thick irreducible building of rank n ≥ 2 satisfying the Moufang condition if n = 2.

• 3. G is an alternating group or one of the 26 sporadic groups.

Each group in case (1) is a 2-transitive permutation group on a set X having a conjugacy class of subgroups {U _x ∣x ∈ X} such that for each x ∈ X, U _x fixes x and acts sharply transitively on X∖{x}. A permutation group satisfying these properties is called a Moufang set. Moufang sets have not been classified without the assumption of finiteness. Although considerable progress toward a classification of arbitrary Moufang sets has been made in recent years (see, in particular, [3]), this seems to be a very difficult problem.

The finite simple groups in cases (1) and (2) are the groups of Lie type. More precisely, the groups in case (1) are the groups of Lie type of rank n = 1 and those in case (2) are the groups of Lie type of rank n. The groups in case (1) also have associated buildings, but these buildings are of rank 1. As we observed in the previous section, buildings of rank 1 are simply complete graphs. The underlying set of chambers of this building is precisely the set X on which the group forms a Moufang set.

A finite building has, of course, finite apartments and is thus automatically spherical. As we have seen in the previous section, thick irreducible buildings of rank n ≥ 2 satisfying the Moufang condition if n = 2 can all be described in terms of suitable algebraic data. The assumption that the building (and hence the algebraic data) is finite imposes severe restrictions on the types of algebraic structures that can occur, as we now explain.

Suppose, to start, that the Coxeter diagram Π of our building Δ is A _n , D _n or E _n for n = 6, 7 or 8. There are no finite non-commutative skew-fields, no finite octonion division algebras and just one field $\mathbb{F}_{q}$ for each prime power q. Thus Δ is uniquely determined by Π and a prime power q. The corresponding simple groups G ^† are

$$\displaystyle{A_{n}(q) = \mathrm{PSL}_{n+1}(q),D_{n}(q) = \mathrm{O}_{2n}^{+}(q)\ \text{and}\ E_{ n}(q).}$$

Suppose that Π = F ₄. We saw in the last section that Δ is determined by an anisotropic quadratic space (K, L, Q) in one of five cases (1)–(5). (We use an uppercase Q here rather than q for the quadratic form, since in this section q is always a prime power.) In fact, Δ depends only on the similarity class of this quadratic space. By finiteness $K = \mathbb{F}_{q}$ for some prime power q. Furthermore, there are only two anisotropic quadratic spaces over $\mathbb{F}_{q}$ up to similarity: either L = K and Q(x) = x ² for all x ∈ L or $L = \mathbb{F}_{q^{2}}$ and Q is the norm of the extension L∕K. Each of them does, in fact, give rise to a unique building of type F ₄. The corresponding simple groups are

$$\displaystyle{F_{4}(q)\ \text{and}\ ^{2}\!E_{ 6}(q^{2}).}$$

(The superscript in the name $^{2}\!E_{6}(q^{2})$ indicates that this group can be constructed as the centralizer in the group $E_{6}(q^{2})$ of an outer automorphism of order 2 that involves the element of order 2 in the Galois group of the extension L∕K. In fact, we can interpret the rank 1 groups U ₃(q), Suz(q) and Ree(q) analogously as $^{2}\!A_{2}(q^{2})$,²​B ₂(q) and²​G ₂(q), where B ₂(q) and G ₂(q) are as described below.)

Suppose that Π = G ₂. The relevant algebraic structure in this case is a “quadratic Jordan division algebra of degree 3;” see Chapter 15 of [12] for details. Let J be the underlying vector space over a field K of one of these algebras. In the finite case, $K = \mathbb{F}_{q}$ for some prime power q, either J = K or $J = \mathbb{F}_{q^{3}}$ and in both cases the Jordan algebra is uniquely determined by q. The corresponding simple groups are

$$\displaystyle{G_{2}(q)\ \text{and}\ ^{3}\!D_{ 4}(q^{3}).}$$

Suppose that n = 2 and that the Moufang polygon associated with Δ is an octagon. In this case, Δ is defined by a pair (K, σ), where K is a field of characteristic 2 and σ is an endomorphism of K whose square is the Frobenius map x↦x ². In the finite case, K is the field with q = 2^m elements for some odd m and for each odd m, the endomorphism σ is unique. The corresponding simple group is

$$\displaystyle{^{2}\!F_{ 4}(q).}$$

Suppose next that Δ is one of the two buildings B _n (K, L, Q) or C _n (K, L, Q) for some anisotropic quadratic space (K, L, Q) described in Sect. 5. Then $K = \mathbb{F}_{q}$ for some prime power q and, as in the case F ₄, either L = K and Q(x) = x ² or $L = \mathbb{F}_{q^{2}}$ and Q is the norm of the extension L∕K. If | L |  = q, the simple groups coming from B _n (K, L, Q) and C _n (K, L, Q) are

$$\displaystyle{\mathrm{O}_{2n+1}(q)\ \text{and}\ \mathrm{PSp}_{2n}(q).}$$

and when | L |  = q ², they are

$$\displaystyle{\mathrm{O}_{2n+2}^{-}(q) =\, ^{2}\!D_{ n+1}(q^{2})\ \text{and}\ \mathrm{U}_{ 2n}(q) =\, ^{2}\!A_{ 2n-1}(q^{2}).}$$

If L = K and char(K) = 2, then the root group sequence Ω in (7) is isomorphic to its opposite and hence B _n (K, L, Q) is isomorphic to C _n (K, L, Q). Therefore $\mathrm{O}_{2n+1}(q)\mathop{\cong}\ \mathrm{PSp}_{2n}(q)$ for q even. When n = 2, this is the group referred to as B ₂(q) above.

There is just one more family of finite buildings with Coxeter diagram Π = B _n , one for each prime power q. These are the buildings described in [20, 30.14(vii)] that are finite. They yield the simple groups

$$\displaystyle{\mathrm{U}_{2n+1}(q) =\, ^{2}\!A_{ 2n}(q^{2}).}$$

These are the only finite buildings of type B _n not all of whose root groups are abelian. Let q be a prime power and let Δ be the corresponding building. The non-abelian root groups of Δ can be described as follows. Let L∕K be the unique quadratic extension with | K |  = q, let N be the norm of this extension, let σ be the unique non-trivial element in Gal(L∕K), let $\beta =\alpha -\alpha ^{\sigma }$ for some α ∈ L not contained in K and let S be the set {(a, b) ∈ L × L∣α N(a) − b ∈ K} endowed with the multiplication

$$\displaystyle{(a,b) \cdot (c,d) = (a + c,b + d +\beta a^{\sigma }c).}$$

Then S is a group of order q ³ whose center is (0, K), where

$$\displaystyle{(a,b)^{-1} = (-a,-b^{\sigma })}$$

for all (a, b) ∈ S. Every root group of Δ is isomorphic either to S or to the additive group of K.

7 Affine Buildings

Another celebrated result of Tits is his classification of affine buildings in [11]. A connected Coxeter diagram is called affine if it is the Coxeter diagram $\tilde{X}_{n}$ underlying the extended Dynkin diagram attached to the Dynkin diagram X _n for X = A, B, C, D, E, F or G and for some n ≥ 1, and a building with Coxeter diagram Π is affine if each connected component of Π is affine. (See the figure on page 1 of [20].)

Suppose that Ξ is a thick irreducible affine building. Thus its type Π is $\tilde{X}_{n}$ for some X and n. The apartments of Ξ have a natural embedding into a Euclidean (or affine) space of dimension n. For this reason, affine buildings are sometimes called Euclidean buildings. The principle structural feature of the building Ξ (apart from its apartments and residues) is its building at infinity, Δ: = Ξ ^∞. The building Δ is thick and of type X _n and thus spherical and irreducible. (If X _n  = A ₁, then Ξ is a tree, Δ, a building of rank 1, is the set of ends of this tree and the apartments of Ξ, which are the connected subgraphs of valency 2, can be thought of as Euclidean spaces of dimension 1.) We call Ξ a Bruhat-Tits building if its building at infinity Δ satisfies the Moufang condition (which requires that n ≥ 2). These are the buildings studied systematically in [1]. By Theorem 8, Ξ is automatically a Bruhat-Tits building if n ≥ 3, but not if n = 2. What Tits showed is that Ξ is uniquely determined by Δ if n ≥ 2 and that a given thick, irreducible spherical building satisfying the Moufang condition is the building at infinity of a Bruhat-Tits buildings if and only if the defining field K of Δ as defined at the end of Sect. 5 above is complete with respect to a discrete valuation. (This statement is not quite accurate if the algebraic data determining Δ is infinite dimensional or in certain other ways “exotic”, but it is not so far from begin accurate. See Chapter 27 of [20] for exact statements.) Thus the theory of Bruhat-Tits buildings brings out deep connections not just between group theory and geometry but number theory as well.

Of particular interest both to number theorists and to differential geometers is the case that Ξ is locally finite (in the usual sense of graph theory). This corresponds to the special case that the field K is a local field, by which we mean not only that K is complete with respect to a discrete valuation, but also that the residue field of K is finite. Every local field is a finite extension of a p-adic field for some prime p or a field of Laurent series over a finite field. In the locally finite case, it is possible to carry out a precise classification of all the possible algebraic structures that can occur in the spirit of the previous section. For example, if (K, L, q) is an anisotropic quadratic space and K is a local field, then dim _K L ≤ 4 and if dim _K L = 4, then q is the reduced norm of a quaternion division algebra with center K and, furthermore, there is only one such quaternion division algebra. See Chapter 28 of [20] for all the details.