Theory Update 77

In this paper, Loday shows that the minimal number of simplices required to construct an associahedron is $(n + 1)^{n - 1}$. In particular, in dimension $3$ we need $16$ tetrahedra to form the associahedron.

These are labeled by the parking functions on three elements, using triangles on $2/3$ of the associahedron, as shown. This is the list of all possible permutations of sequences $n_1 n_2 n_3$ in the numbers $1$, $2$ and $3$, such that the ordered sequence has $n_1 = 1$, $n_2 \leq 2$ and $n_3 \leq 3$. Observe the $S_3$ permutation group around the source vertex for the polytope, where the orientation of edges is given by the sequence labels.

Since (real) moduli spaces are tiled by associahedra, they are now given a canonical realisation in terms of simplices. The set of parking functions $P_n$ for general $n$ is given by an inductive formula, using the set $P_p \times P_q$ for $p + q = n - 1$. The set $P_n$ always labels the simplices that fill in an associahedron.

Parking functions are interesting combinatorial gadgets. McCammond outlines their connection to non crossing partitions, which themselves are related to the Narayana number grading on the associahedra. For example, the non crossing partitions for a $d = 4$ element set sit on a lattice of height $3$, with a total of $14$ elements. These are the $14$ vertices of the associahedron above. In total, there are $15$ partitions on a $4$ element set. The missing partition is a square with crossing chords.

The lattice of non crossing partitions is also realised as a Brady-Krammer complex, which happens to be an Eilenberg-MacLane space for the braid group $B_{d}$. In the height $3$ lattice for square partitions, one has paths of length $0$, $1$, $2$ or $3$, which are used to define the complex.