Strange AssociationsThere are many other polytopes that can be described in purely combinatorial terms. Among the more curious are the associahedra....
A polytope of
In three dimensions they are polyhedra, such as these familiar ones:
There is a vast theory of such geometrical objects. The most interesting ones are those with some important connection to branches of mathematics other than geometry, for example bringing to light situations where geometry says something about algebraic structures. In this note, I'll say something about the polytopes known as associahedra, and try to say something about their algebraic significance as well.
This is not at first sight a lovable figure, not elegantly symmetrical like the more familiar regular polyhedra, and indeed to all appearances assembled rather randomly. But then true beauty is never based on superficial appearances, is it?
I'll start with the ... well, simplest ... examples of polytopes. They are called simplices (singular: simplex). Suppose we are given in
The faces of any polytope are ... well, its faces - the flat subsets making up its boundary. They come in different dimensions. The vertices are its extremal points, its edges are the links between neighbouring vertices, and so on. For a simplex, the faces are simplices of lower dimension, parametrized precisely by the subsets of its vertices (all of them but the empty set, and sometimes it is thrown into the collection as well). In two dimensions the faces of triangle
For a tetrahedron associated to
The faces of any polytope make up a set with an order relation: One face is considered to be less than another when it is properly contained in it. For simplices, one face is less than another when its parametrizing subset is contained in that of the other. Thus the edge
Exercise. The convex hull in
The face graph of a polytope
The essential nature of a polytope lies somewhere in between its metric structure and its topological structure. We don't care about the exact size of things. All tetrahedra are equivalent in this business, but we do want to distinguish between a tetrahedron and a cube, even though they have the same topological structure (since both can be smoothly deformed into a sphere). This combinatorial structure is pretty much captured by the face graph of the polytope that displays the set-plus-order I have mentioned above, and does this so that all faces of the same dimension are somehow seen to be of that dimension. This I'll call a ranked graph - that is to say, each node of the graph is assigned a rank (here, the dimension of the face) and if one node is less than another than it has lower rank. Here is the face graph of the triangle
One very general question considered in this theory is, How can one tell whether a given ranked graph is the face graph of a polytope? This can be a very, very difficult question, even for a particular graph.
The essential nature of the simplex lies in its face graph, but this can be described in purely combinatorial terms - i. e. purely in terms of the subsets of its set of vertices, and the way they are contained in one another. There are many other polytopes that can be described in purely combinatorial terms. Among the more curious are the associahedra. I describe first the combinatorial object.
Start with a product
Inserting two pairs you get
You can't insert any more, according to the rules.
At first it might seem that this is a largely messy process. But now I associate to these lists its face graph. At its top is
which can be rearranged to look like this:
Thus, we see that the associahedron
(There is a systematic way to make this list - list first all expressions where the ( occurs at the far left, then where it occurs between the first and second characters, etc.) These parametrize the two-dimensional faces of
Even when one knows that a given combinatorial structure comes from a polytope, it is not necessarily a trivial matter to construct it explicitly. This is certainly true of associahedra. The very first description of an associahedron is to be found in the Ph. D. thesis of the topologist Jim Stasheff, but he was unable to represent it as a strict polytope. Instead, he had to be content with a somewhat curvy shape. Here is his
Of course, it is easy to see how to modify this to be a true polytope. In fact, John Milnor showed up at Stasheff's thesis defense with a cardboard model. But is is not at all easy to see how to straighten out Stasheff's curvy associahedron in all dimensions.
There are by now many, many constructions of the associahedron as a true polytope. Nearly all of them are intimately related to some deep theoretical understanding of the structure, but ultimately there is some more or less arbitrary decision to be made. This is what one expects, since after all the "essence" of the shape is not, as I have said, in its explicit metric structure.
What seems to be the the simplest rendering in all dimensions is that of Loday. He sets this up in terms of a natural tree structure associated to a well-balanced expression, but I'll describe it in ternms of the expression itself. It works by mathematical induction on the length of the expression.
Here is Loday's very pretty result:
Theorem. The associahedron of dimension
(Hidden edges are in red.)
The history of associahedra is curious. They were first constructed by the topologist Jim Stasheff in his 1961 Princeton University thesis, where they were used to explore various kinds of topological associativity. Stasheff tells me that his thesis was received with no fanfare, and that in fact he had some trouble getting his research published. It was turned down by one prestigious journal, then accepted by the Transactions of the American Mathematical Society.
Nonetheless time passed, and after a while things began to appear in a different light. Stasheff's work was taken up into the theory of operads, of importance today in physics as well as in homotopy theory. Independently, around 1978 these structures were rediscovered, but this time by combinatorialists instead of topologists. The combinatorial structure of associahedra was specified as I have given it here in a paper by Huguet and Tamari, and it was asserted without proof by them that this was the face-graph of a polytope. I am not sure what the background to that construction was, but Gil Kalai tells me that Tamari had been interested in general questions of associativity in algebra since his thesis of 1951.
It was Kalai himself who named this structure an associahedron, and he called the problem of constructing the polytope explicitly to the attention of Mark Haiman, who then wrote down what was apparently the first detailed proof. From that point on, the subject expanded rapidly, but Stasheff's priority and the connection of associahedra with homotopy theory was not recognized by the combinatorialists until Mikhail Kapranov pointed it out. He was one of the first to extend significantly the family of associahedra to include other polytopes of combinatorial interest. The interest in associahedra and related polytopes continues to rise. New relations with widely spread fields of mathematics are still appearing.
Developments have taken place in several different directions, all rather intriguing developments for such an intrinsically simple object. One closest to the original combinatorial invention is that explained in work of Satyan Devadoss (and a colleague or two) which associates a polytope rather explicitly to any finite graph whatsoever. Simplices come from a collection of unconnected nodes, associahedra from lines of connected ones. This is Devadoss' rendering of
To find out more
Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Some of the items above can be accessed via the ACM Portal , which also provides bibliographic services.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance