reference for the cubical structure of the associahedra

Question

I cannot find where I learned that the $n$-dimensional associahedron is a union of $n$-cubes. The vertices of the $n$-dimensional associahedron are the finite binary trees having $n+2$ leaves and there is one cube for each vertex (tree). If the internal edges of the tree (those edges whose endpoints both do not have valence one) are allowed to independently take on any length in the unit interval $[0,1]$, then these "distorted" trees parametrize the cube. (There are $n$ internal edges, so we get an $n$-cube.)

Does anyone know exactly where this parametrization of the cubical structure is written down? I know I cannot eliminate "guess" responses, but let me try by saying that I have checked all the reasonable guesses and have not found it. I know it is out there. Does anyone know where?

Answer 1

Seeing the OP's comment above summarizing what's been said so far, I get the impression he's hoping for further elaboration of how to decompose an associahedron into cubes. I found it interesting to think about how David Speyer's answer and Ian Agol's answer fit together, so let me take a shot at explaining that. While tree space is more complicated than an associahedron, it is a natural place to talk about the connection between trees, edge lengths, associahedra, and its cubical subdivision.

The star of the origin in the space of phylogenetic trees can be viewed as a union of associahedra, each decomposed into cubes in a natural way which amounts to exactly the construction Agol describes. We get one such associahedron sitting inside the star of the origin for each way of labeling the $n$ leaves of a binary tree with the numbers $1,\dots ,n$ up to cyclic rotation of the leaf names, so altogether we get $(n−1)!$ associahedra. In other words, an associahedron sitting inside tree space is specified by a permutation in $S_n$ in one line notation up to cyclic rotation as follows: choose a leaf arbitrarily to serve as the root of a planar tree whose leaves are labeled $1,\dots ,n$ in some order, then record the ordered sequence of leaf labels (including the root) which we encounter in a depth first search of the planar tree where we proceed from left to right through the children of each node. Choosing a different root just amounts to cyclic rotation of this sequence.

While tree space is defined more abstractly, not referring to a planar embedding, the point is for each tree to be comprised of (1) ``edges'' which are precisely set partitions with two blocks -- specifying how the leaves of a tree get split into two distinct, connected components when just that edge is deleted from the tree, and (2) edge lengths, which are nonnegative real numbers. This data can be read off from the above planar trees, and is used to construct tree space (and within tree space associahedra that are naturally decomposed into cubes). This is done as follows.

Any binary tree with leaves labeled $\pi(1),\dots ,\pi(n)$ for $\pi\in S_n$ gives rise to an orthant ${\mathbf R}^{|E|}_{\ge 0}$ within ``tree space'', where $|E|$ is the number of internal edges; each nonnegative coordinate specifies the length of the internal edge indexing that coordinate. One reaches the boundary of an orthant by letting edge lengths degenerate down to $0$, causing internal nodes to have degrees higher than 3 at these degenerate trees. Tree space is obtained by gluing together these orthants where these degenerate boundary trees actually coincide.

The collection of orthants coming from any particular choice of permutation $\pi $ gives exactly an associahedron, and its subdivision into these orthants is precisely the cubical subdivision Agol describes. Every orthant has the origin in its boundary, making it reasonable to focus on the star (or link) of the origin. The OP's requirement of edge lengths at most 1 yields finite cubes within the orthants, which exactly coincide with the cubes Agol describes. The origin is at the center of the associahedron, while letting more and more edge lengths increase from 0 to 1 yields midpoints of lower and lower dimensional faces of the associahedron.

Another interesting related paper is:

Federico Ardila and Caroline Klivans, The Bergman complex of a matroid and plylogenetic trees, J. Combinatorial Theory, Ser. B, 96 (2006), 38--49.

This paper proves that the link of the origin in tree space is homeomorphic to the order complex of the proper part of the partition lattice, which also tells us that the link of the origin in tree space is homotopy equivalent to a wedge of $(n-1)!$ spheres, each of dimension $n-3$. I suppose this strongly hints that the $(n-1)!$ associahedra mentioned above are probably a homology basis for the link of the origin in the space of phylogenetic trees.

Answer 2

I learned this picture from Billera, Holmes and Vogtman; see Figure 18. Their focus in on describing the space of all trees, not just the planar ones, so they have many associahedra glued together instead of just one, but they certainly talk about the individual associahedra.

Answer 3

I think this is just the cubical barycentric subdivision of the associahedron. The faces of the associahedron correspond to planar trees with $n+2$ leaves (say with vertices labelled by cyclic order). Insert a new vertex into the interior of each face of the associahedron for each planar tree, and connect two of these vertices by an edge if they differ by contracting an interior edge, which corresponds to containment of faces. Then the cubes you describe associated to each planar tree give rise to cubical barycentric subdivision.

I think another description may be obtained as a cube complex associated to the wall space, where one takes $n+2$ vertices on a circle, and the walls are all ways of dividing the vertices into two two sets of contiguous vertices (with at least two vertices in each set). One has a wall associated to each interior edge of a planar tree with leaves on the vertices, since it divides the vertices into two sets. Chatterji-Niblo show how to associate a cube complex to any wall space, and I believe in this case it gives rise to the cubical subdivision of the associahedron. In fact, this then shows that it is also a CAT(0) cube complex.