The ADE affair, 1

In the 1970s, the American Mathematical Society held a symposium on Mathematical developments arising from Hilbert problems. Each of Hilbert’s problems was described, and subsequent progress and developments traced, by at least one expert in the area. As part of the occasion, Felix Browder asked various eminent mathematicians to supply what they considered to be significant problems in the spirit of Hilbert. The collection is published in the proceedings of the symposium.

One of the mathematicians who responded was Vladimir Arnol’d. He posed a rather different kind of problem, that of explaining the ubiquity of the famous Coxeter–Dynkin diagrams of type ADE throughout mathematics. He noted their occurrence in areas such as Lie algebras (classification of simple Lie algebras over the complex numbers), Euclidean geometry (root systems), group theory (Coxeter groups), representation theory (algebras of finite representation type), and singularity theory (singularities with definite intersection form), as well as their connection with the regular polyhedra.

Since then, more occurrences have come to light. In this short series of posts I will take a look at some of these and explore some of the connections. I do not come to a definite answer to Arnol’d’s question, however. My rough plan is to introduce the diagrams and talk about their occurrence in n dimensions in this post, their occurrence in 3 dimensions in the next, and the recent topic of clusters in the third; the fourth will be a cautionary tale; and the fifth will consider the Coxeter–Dynkin diagrams with multiple bonds (the BFG affair).

But it should be absolutely clear that the diagrams are combinatorial objects, and that their defining property (underlying their occurrence throughout much of mathematics) is a simple fact of algebraic combinatorics.

The ADE diagrams

Here are the famous ADE diagrams. There are two infinite families and three sporadic ones.

ADE diagrams

The restriction to n≥4 for type D is made because D2 is disconnected (consisting of two disjoint nodes), while D3 is the same as A3 (a path of three nodes). Note also that E4 would be the same as A4 and E5 the same as D5.

We will also need the extended diagrams, each of which is obtained by adding a node to the ordinary diagram as follows:

  • An*: join the new node to the end of the path An, producing a cycle;
  • Dn*: join the new node to the penultimate vertex of Dn, producing a “fork” at each end (except for D4*, which is a “star” with four arms);
  • En*; join the node to the end of one “arm”, producing arms of lengths 2,2,2 (for E6*), 1,3,3 (for E7*), and 1,2,5 (for E8*).

There are more general diagrams with multiple bonds, which I will not discuss here. These will come in (much) later.

The characterisation is as follows:

The ADE diagrams are precisely the connected graphs with greatest eigenvalue strictly less than 2.

(The eigenvalues of a graph are those of its adjacency matrix.) Since this is the crucial property, I will give a proof.

The proof depends on the fact that the greatest eigenvalue of a principal submatrix of a symmetric real matrix cannot exceed that of the whole matrix. This in turn follows from the obvious fact that a principal submatrix of a positive semidefinite matrix is positive semidefinite (applied to λIA, where λ is the greatest eigenvalue).

Now the extended diagrams all have greatest eigenvalue 2. (By Perron–Frobenius, this simply requires us to label the nodes with positive numbers so that the label of each node is half the sum of the labels of its neighbours: a pleasant exercise). So a graph with greatest eigenvalue less than 2 cannot contain any extended diagram as an induced subgraph.

In particular, such a graph has no cycle, so is a tree; has no node of degree 4 and at most one of degree 3, so consists of three arms radiating from a common node. The En* diagrams restrict the lengths of the three arms to those given.

There is more to be said. It can also be shown that the extended diagrams are precisely the connected graphs with greatest eigenvalue 2. The proof above shows that a connected graph has greatest eigenvalue less than 2 if and only if it doesn’t contain a subgraph with greatest eigenvalue 2. It is not known which values λ of the greatest eigenvalue have this property; most values do not!

Root systems

A root system is a finite set S of nonzero vectors in a real vector space (with positive definite inner product) such that

  • for any sS, we have csS if and only if c=±1;
  • S is mapped to itself by the reflection in the hyperplane perpendicular to s, for any sS (this reflection has the formula rs(x)=x−(2x.s/s.s)s);
  • the coefficient 2x.s/s.s in this reflection is an integer for all x,sS (this is called the crystallographic condition).

We always assume that a root system is indecomposable, that is, not contained in the union of two proper orthogonal subspaces.

Consider the case where all the vectors in S have the same length. Then we may assume that s.s=2 for all sS; then we have x.s=2, 1, 0 −1 or −2 for all x,sS; that is, any two of the vectors which are not equal or negatives make an angle 60°, 90° or 120°. Moreover, the reflection condition show that if two vectors of S make an angle of 60° or 120°, then the six vectors in the plane they span forming a regular star all lie in S; in other words, S is star-closed. Conversely, a star-closed set of vectors at the appropriate angles is a root system.

It can be shown that a root system has a fundamental basis, all of whose vectors lie at angles 90° or 120°. Any root is an integer linear combination of basis vectors with all coefficients having the same sign. Form a graph by joining vectors of the fundamental basis if their angle is 120°. This graph is connected. If its adjacency matrix is A, then the matrix of inner products of basis vectors is 2IA. Since this is positive definite, the graph has greatest eigenvalue less than 2, so it is one of the ADE diagrams. The diagram uniquely determines the root system.

The root systems have simple explicit representations. Let e1, e2, … be orthonormal basis vectors in an appropriate space.

  • An consists of the n(n+1) vectors eiej for ij, 1≤i,jn+1 (these all lie in the subspace of vectors with coordinate sum zero);
  • Dn consists of the 2n(n−1) vectors ±ei±ej for ij, 1≤i<jn;
  • E8 has several beautiful representations. It consists of
    • 72 vectors of A8 together with all 168 vectors with three coordinates 2/3 and six coordinates 1/3 and their negatives; or
    • 112 vectors of D8 together with 128 vectors with all eight coordinates ±1/2, with product of the signs being +1 (or, for a different representation, product −1); or
    • (after re-scaling) the 16 vectors ±ei together with the 224 vectors with four coordinates ±1/2 and four coordinates 0, the non-zero coordinates forming a plane of affine 3-space over GF(2).

E7 and E6 can be obtained by choosing appropriate subspaces of E8.

For An, a fundamental basis consists of the n vectors e1e2, e2e3, …, enen+1.

Coxeter groups

Let S be a root system of the type just described. Then the reflections rs, for sS, generate a group which preserves S, and so is finite since S contains a basis. The generating reflections all have order 2. Moreover, rsrt has order 2 if s and t are orthogonal, and order 3 otherwise.

In fact, the crucial information is contained in the diagram. The nodes correspond to vectors in a fundamental basis, and the corresponding reflections generate the group. Now the product of the two generators has order 3 if the nodes are joined by an edge, or 2 if not.

Thus we can regard the diagram as encoding a presentation of a group, with generators of order 2 and the orders of their pairwise products prescribed. Clearly there is a homomorphism from this abstract group to the reflection group.

Coxeter showed that the homomorphism is faithful, so that the diagram is a presentation of the reflection group.

In the case of An, the group is our old friend the symmetric group Sn+1; the reflection corresponding to the root eiei+1 being the transposition (i,i+1).

There is much more to Coxeter’s Theorem than this. It gives a complete classification of finite groups generated by reflections in Euclidean space, and provides a presentation of the above form (concisely described by a diagram) for every such group. More on this later.

Lie algebras, BN-pairs

The material here will only be mentioned, since all root systems are relevant, not just those with roots all of the same length. Here is a very brief account.

A Lie group is a differentiable manifold which is also a group. The group structure induces a Lie algebra structure in the tangent space at any point.

Root systems arose first in the classification by Cartan and Killing of simple Lie algebras over the complex numbers. There is an Abelian subalgebra, the Cartan subalgebra, carrying the non-degenerate Killing form; the whole algebra is spanned by this subalgebra and a collection of 1-dimensional root spaces. Each root space induces a linear map on the Cartan subalgebra, and so corresponds to a vector in the dual. These vectors form a root system, whose structure determines the algebra.

Now information in the tangent space can be lifted to the group by an “exponentiation” procedure. The resulting structure in the group can be abstracted to the notion of a BN-pair; BN-pairs occur in other situations, such as simple algebraic groups and finite simple groups of Lie type. An important ingredient of a BN-pair is its Weyl group, the reflection group corresponding to the root system.


I will spend a bit longer on this since it includes my own contribution to the subject, a 1979 paper with Jean-Marie Goethals, Jaap Seidel and Ernie Shult.

We saw that the ADE diagrams and their extensions are the connected graphs with greatest eigenvalue at most 2. One could ask, dually, which connected graphs have smallest eigenvalue at least −2?

This problem was considered by Alan Hoffman, after special cases had been solved earlier by Hoffman and others (including Shrikhande, whose work I discussed last year). Hoffman came up with the notion of a generalized line graph, defined as follows.

First we define a cocktail party graph on 2n vertices: the vertices are paired up, and each vertex is joined to all except the one paired with it. (Apparently, a cocktail party consists of a collection of couples, and each person talks to everyone except his/her partner.)

Now let G be a graph, and f a function assigning a non-negative integer to each vertex. The generalized line graph L(G,f) is defined as follows: its vertices are the edges of G together with cocktail party graphs of sizes 2f(v) for each vertex of G; edges of the generalized line graph join edges of G sharing a vertex, while the cocktail party corresponding to v is joined to all edges through v, and we retain all edges of the cocktail parties. Note that in particular, if f=0 then we just have the ordinary line graph of G, while if G has a single vertex we have a cocktail party graph.

In an unpublished manuscript, Hoffman showed that all “sufficiently large” connected graphs with smallest eigenvalue −2 or greater are generalized line graphs. Root systems give a much simpler and more transparent approach to this result.

Let A be the adjacency matrix of a graph with smallest eigenvalue at least −2. Then A+2I is positive semidefinite symmetric, it is the matrix of inner products of a set of vectors in some Euclidean space. Since A+2I has diagonal entries 2 and off-diagonal entries 0 or 1, the vectors have squared length 2 and make angles of 60° or 90° with each other.

Now enlarge this set to a set maximal with respect to having squared lengths 2 and inner products in {−2,−1,0,1,2}. A simple argument shows that such a set is star-closed, so is a root system, of one of the types ADE. The connectedness of the original graph shows that the root system is indecomposable. We say that the graph is represented in the root system. Now the following technical results are easy to establish:

  • a graph is represented in the An root system, for some n, if and only if it is the line graph of a bipartite graph;
  • a graph is represented in the Dn root system, for some n, if and only if it is a generalized line graph.

Hence we have shown:

A connected graph with smallest eigenvalue −2 or greater is either a generalized line graph, or representable in the root system E8.

Clearly only finitely many graphs are represented in E8. So Hoffman’s Theorem follows.

This result has led to a lot of developments in the study of such graphs; but that is enough for today!



About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, history and tagged , , , , . Bookmark the permalink.

One Response to The ADE affair, 1

  1. Pingback: Weekly Picks « — the Blog

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s