# Combinatorics of the Stasheff polytopes

First a little background for those unaware. The Stasheff polytopes (or associahedra) are certain convex polytopes that arise in the theory of $A_\infty$-algebras. There is one polytope for each $n\geq 2$ and is denoted by $K_n$. The $K_n$'s essentially encode the homotopies, higher homotopies and so on of the associativity relation. One way to describe $K_n$, which is has dimension $(n-2)$, is to take all rooted binary trees with $n$ leaves and take a suitable convex hull. For example, $K_2=\{\ast\}$, $K_3$ is an interval while $K_4$ is a pentagon.

It is known that the number of vertices $v$ of $K_n$ is the $(n-1)^{th}$ Catalan number, i.e., $v=\frac{1}{n}{2n-2 \choose n-1}$. What can one say about the number of edges of $K_n$ and generally about counting faces of all codimension?

-
The Stasheff polytope is simple, right? so the number of edges is d/2 times the number of vertices, where d=n-3 is the dimension. I think there are formulas for all the face numbers. –  Gil Kalai Nov 21 '09 at 15:57
Using the simplicity to get the formula for edges is an elementary but nice method. I like it! –  Somnath Basu Nov 21 '09 at 17:30
S. Devadoss and J. O'Rourke have some interesting presentations of the associahedra in their book Discrete and Computational Geometry. –  Tom Copeland Sep 6 '12 at 7:40

After a change of variables, the answer is sequence A033282 in the Encyclopedia of Integer Sequences: $T(n,k)$ is the number of diagonal dissections of a convex $n$-gon into $k+1$ regions. The page gives the wonderful formula, $$T(n,k) = \frac{1}{k+1}\binom{n-3}{k}\binom{n+k-1}{k},$$ for relevant values of $k$.

I find it easier to also keep track of the dual Stasheff polytope, which can be realized as a simplicial complex based on dissections of a convex polygon. The polytope $K_n^*$ has a vertex for each diagonal of an $(n+1)$-gon, and it has a face for every collection of disjoint diagonals. So, in terms of your original parameters, $K_n$ has $T(n+1,n-2-k)$ faces of dimension $k$.

Also: One reason that I like the dual Stasheff polytope is that it has an amazing infinite generalization called the Hatcher-Thurston arc complex. You again take collections of disjoint arcs that connect marked points, but in the generalization you can take any surface with or without boundary, as long as it has at least one marked point total and at least one on each boundary component. (And I suppose in the disk case it needs at least three marked points.) Each isotopy class of arcs is a vertex, and each disjoint collection is a face. It is a combinatorial model of Teichmüller spaces or moduli spaces of curves (with the requisite marked points).

Gil Kalai in the comments asks for a few more details of the Hatcher-Thurston arc complex, and he gives a reference to one of the original papers, "On triangulations of surfaces, Topology Appl. 40 (1991), 189–194," by Allen Hatcher. Briefly: Suppose that $\Sigma$ is a fixed surface with some marked points. There should be enough marked points so that there exists at least one generalized triangulation of $\Sigma$ whose vertex set is the marked points. A question that could be taken as motivation is the following: Can you find a complete set of moves on triangulations, moves on moves, moves on moves on moves, etc.? Whether the set of moves is complete is not entirely a rigorous question, but there is an interesting answer. The moves and higher moves just come from erasing edges of the triangulation. The main theorem is that the resulting simplicial complex is contractible. The mapping class group acts on the complex, and it acts freely on the high-dimensional simplices.

More precisely, the arc complex has a vertex $v$ for every isotopy class of an arc between two of the marked points, among properly embedded arcs that miss all of the marked points in the interior. If a collection of arcs can be made disjoint after isotopy, then the corresponding vertices subtend a simplex. The disk case is an exception in which the arc complex is not quite contractible, but rather a sphere.

-
Thanks a lot! I knew the diagonal dissections of a convex polygon idea but somehow couldn't get any explicit formula out of it. I came up with a recursive (ala generating functions) defintion of $T(n+1,n+2-k)$ which can now be checked with what you said. –  Somnath Basu Nov 21 '09 at 17:20
I forgot to add before but the Teichmuller space viewpoint is indeed amazing! –  Somnath Basu Nov 21 '09 at 17:33
This observation that the dual is a finite-dimensional version of the Hatcher-Thurston complex, has someone written that down somewhere in the literature, other than here? –  Ryan Budney Nov 21 '09 at 19:21
For instance, it is mentioned by Fomin, Shapiro, and D. Thurston, arXiv.org/abs/math/0608367. –  Greg Kuperberg Nov 21 '09 at 19:44
Greg, is this the original paper where the Hatcher-Thurston objects defined? A. Hatcher, On triangulations of surfaces, Topology Appl. 40 (1991), 189–194. Also can you describe the construction in a little more detail? –  Gil Kalai Nov 22 '09 at 7:00

Greg's explanation is way too complicated for a simple problem. Here is a more direct combinatorial approach. I know this is an old question, but just for the record.

Fix a convex $n$-gon $Q \subset \Bbb R^2$ with set of vertices $V$. Consider a Gelfand-Kapranov-Zelevinsky realization of the associahedron in the space of functions: for every triangulation $T$ of $Q$, take $f_T: V \to \Bbb R$, where $f(v)=$area of triangles with vertex at $v \in V$. Now consider a linear function $\phi: \Bbb R^n \to \Bbb R$ by setting $$\phi(x_1,\ldots,x_n) = x_1 + \epsilon x_2 + \ldots \epsilon^{n-1} x_n,$$ where $\epsilon >0$ is very small. Now, the triangulations $T$ of $Q$ correspond to binary trees and the edges of the associahedron are the pairs of triangulations obtained by a flip - the change of an edge in a quadrilateral. In the language of binary trees, these correspond to the edges as well. Let us compute the $h$-vector of the associahedron. Recall that the index$(T)=$ the number of edges of $Q$ where $\phi$ is increasing, and observe that it is equal to the number of right edges in the corresponding binary tree. Thus $h_i$ is equal to the Narayana number: $$h_i = \frac{1}{n} \binom{n}{i}\binom{n}{i+1}$$ (you need to shift $n\gets n-2$ here). Now the $f$-vector can be obtained via binomial identities: $$F(t) = H(t+1), \ F(t)=\sum_k f_k t^k, \ H(t)=\sum_k h_k t^k$$ To see this example more carefully explained, see my book (chapter 8). For more on the associahedron and the ideas behind the GKZ realization, see Ziegler's Lectures on polytopes (chapter 4).

-