MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Many of you will recognize these as the ADE diagrams, festively colored for the holidays!

alt text

Does anyone know a mathematical interpretation for these diagrams, when colored like this?

Edit: the answers below seem to treat the set of red nodes and the set of green nodes as essentially equivalent. However in the combinatorics relevant to me, the red and green ones play slightly different roles; does this also happen in the Coxeter group story?

share|cite|improve this question
Not to be too Scrooge-like, but if this is a "question" where you already know the answer, then I'm not sure it should go here on MO rather than on a blog post. On the other hand, if the question is open, then perhaps you should make that clearer? – Yemon Choi Dec 13 '10 at 8:54
To answer the question in the title, I suspect Rosie the Red-nosed Reindeer. She's green with jealousy that Rudolph is the one everyone sings about when it's actually her that's out leading the sleigh. – Loop Space Dec 13 '10 at 11:40
As others have noted, this way of partitioning vertices of the underlying Coxeter graph (a tree) plays a key role in the study of the Coxeter number along with eigenvalues of a Coxeter element in a finite Coxeter group. This developed through case-by-case work of Coxeter (1952) and more uniform methods of Coleman (1958): see Bourbaki V.6 or Chapter 3 of my book on reflection groups. No need to omit the graphs of types B, C, F, G here, and no direct connection with Dynkin or Lie theory. Anyway, the colored pictures are an attractive seasonal touch. – Jim Humphreys Dec 13 '10 at 12:18
@Vivek: In the older story about finite Coxeter groups (including the non-crystallographic ones, by the way), there seems to be no special role for your red/green vertices. All that matters is being able to write a Coxeter element as the product of two involutions. At the same time, ADE types have become more prominent than others in some less obvious directions; but it's always a good idea to ask whether newer interpretations have meaning for other types. – Jim Humphreys Dec 13 '10 at 16:21
For anyone coming across this ancient post, the reason I wanted to know what these diagrams meant was I was hoping for a relation to what is going on in pages 11, 12 of . Alas, I at least never found one... – Vivek Shende Mar 13 '13 at 21:41

The nodes correspond to generators of the Weyl group. The red nodes are a commuting set of involutions and so the product is an involution. Similarly for the green nodes. These two involutions generate a dihedral subgroup. The order of the product is the Coxeter number.

share|cite|improve this answer

In the associated Coxeter/Weyl groups there is such an interpretation. Recall that a Coxeter element is the product of the generators ($=$ nodes) in a certain order.

Now red generators commute between themselves, let $L$ be their product; similarly let $R$ be the product of the green generators. Then the product $LR$ is a special Coxeter element called unsurprisingly a bipartite Coxeter element. Note that it is essentially unique since $RL=(LR)^{-1}$.

These special Coxeter elements have figured prominently in recent years in the theory of noncrossing partitions in general Coxeter groups, cf. the memoir by Drew Armstrong for a nice survey, with a combinatorial approach; see also the articles of Brady & Watt for a more geometric approach.

share|cite|improve this answer

Naively, there can be no reasonable way of distinguishing the red nodes from green in the case $A_{even}$, as the Dynkin diagram automorphism switches them.

Less naively, there is indeed a way of distinguishing them in all other cases: the affine Dynkin diagram is also bipartite, and the affine vertex can be taken to be a fixed color. (Unfortunately in your $D_n$ example it would be red, whereas in your $E_6$ example it would be green, so if you're set on those choices I can't help you.)

As others mentioned, you can multiply reds then greens and get a Coxeter element. If you raise it to half its order, you get the long element $w_0$. Of course you can only do this if the Coxeter number is even, which is again all cases except $A_{even}$.

share|cite|improve this answer
I was set on it, but I guess given that your prescription and Jim's prescription give the same answers (why?) maybe I have just messed up my normalization conventions or something. – Vivek Shende Dec 13 '10 at 19:03

Via the McKay correspondence, the nodes correspond to representations of $G$, a finite subgroup of $SU(2)$. If we color the nodes into two groups depending on whether or not the representation pulls back from a representation of $\hat{G}\subset SO(3)$, the image of $G$ under the double cover map $SU(2)\to SO(3)$, we get the coloring pattern that you see. You do need to swap red for green on a couple of your diagrams if you want (for example) green to always be those that don't pull back from $SO(3)$ ("binary" nodes). See Figure 1 here:

share|cite|improve this answer
yeah, at first I thought it must be related to that too, except then when I looked in your paper and saw I had to do the swapping I was upset. Can you think of any meaning for it? – Vivek Shende Dec 13 '10 at 18:53
Another way to think of this coloring is that the extra node in the extended Dynkin diagram is always the color of the representations pulling back from $\hat{G}$ --- the extra nodes always corresponds to the trivial representation. Are you sure that your coloring isn't this one?? – Jim Bryan Dec 13 '10 at 22:55
Consider the character of the central $C_2$ as it acts on an irreducible rep of $G$. Such character of the standard 2-dim rep is nontrivial, hence tensoring with it changes the character. – Bugs Bunny Dec 13 '10 at 23:31

They are bipartite graphs. Some application is in the book

Goodman, l'Harpe, Jones - "Coxeter Graphs and Towers of Algebras"

where they describe how these graphs correspond to Matrices over $\mathbb{Z}$ with norm smaller than 1.

Cf. Theorem 1.1.2 which says there is a 1-1 correspondence between

1) Indecomposable Matrices with entries $\lbrace 0, 1\rbrace$ up to pseudo equivalence

2) Irreducible Coxeter Graphs with bicoloration of type A,D,E

The graphs correspond to Bratelli diagrams of inclusions of finite von Neumann algebras. From these one can construct subfactors with index $4 \cos^2(\pi/n)$ $n=2,3,\ldots$ the index is exactly the square of the associated matrix. These are all possible values $<4$ of the index. See also

Jones Sunders - "Introduction to Subfactors" (eg. chapter 3.3)

share|cite|improve this answer

It is the bypartite graph structure on the corresponding Coxeter diagram.

share|cite|improve this answer

Those are trees, and trees are bipartite as demonstrated by your coloring.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.