Combinatorial polytopes. 120 vertices in 4D, same count as the 120-cell, totally different structure.
Combinatorial polytopes encode discrete data — permutations, bracketings, triangulations — geometrically. Each combinatorial object becomes a point; points differing by a single elementary move become connected.
The permutohedron places the n! permutations as vertices of an (n−1)-dimensional polytope, with edges between permutations differing by an adjacent transposition. The associahedron places the Catalan-many bracketings of n symbols (equivalently, triangulations of an (n+1)-gon) as vertices of an (n−2)-dimensional polytope, with edges between bracketings differing by one associativity move.
The permutohedron is the W-permutohedron for type A: its graph is the Cayley graph of Sn under adjacent transpositions. The associahedron encodes the higher homotopy of associativity (A∞-algebras). The Loday–Ronco projection sends a permutation to the binary tree obtained from its insertion order — a geometric map from permutohedron onto associahedron.
| Polytope | Dim | Vertices | Edges | Facets | Vertex ←→ |
|---|---|---|---|---|---|
| Permutohedron | 2 | 6 | 6 | 6 | permutation of {1,2,3} |
| Permutohedron | 3 | 24 | 36 | 14 | permutation of {1,2,3,4} |
| Permutohedron | 4 | 120 | 240 | 30 | permutation of {1,...,5} |
| Associahedron | 1 | 2 | 1 | 2 | bracketing of 3 symbols |
| Associahedron | 2 | 5 | 5 | 5 | bracketing of 4 symbols |
| Associahedron | 3 | 14 | 21 | 9 | bracketing of 5 symbols |
Table 1. Vertex counts are factorials (permutohedra) and Catalan numbers (associahedra). The three-dimensional permutohedron is the truncated octahedron; the three-dimensional associahedron is an enneahedron with nine facets (six pentagons and three rectangles).
The smallest nontrivial permutohedron has six vertices: the six permutations of . Plot each permutation as a point in using its coordinates directly. All six points lie on the plane , and the two-dimensional figure they form is a regular hexagon. Two permutations are adjacent when they differ by swapping two coordinates whose values differ by one, that is, by an adjacent transposition. The six adjacent transpositions give the six edges of the hexagon.
Figure 1. The permutohedron of . Six vertices labeled with permutations, six edges. Each edge swaps two adjacent values. Press Walk to trace a Hamiltonian cycle: every permutation is visited exactly once, using only adjacent transpositions. This is the Steinhaus-Johnson-Trotter algorithm, and the existence of such a walk is why the Cayley graph of is Hamiltonian.
Every permutation differs from its neighbors by one swap. This is the defining property of the permutohedron's graph. The weak Bruhat order on is generated by the same adjacent transpositions: the number of inversions (pairs out of order) is the Coxeter length, and adjacent permutations in the graph have lengths differing by exactly one.
Four objects have 24 permutations. Plot each as a point in by treating its four values as the coordinates. The 24 points lie on the hyperplane , which is three-dimensional, so the permutohedron of is a 3D polytope. It is the truncated octahedron: a space-filling polyhedron with 8 hexagonal faces and 6 square faces, 24 vertices, and 36 edges. Each hexagonal face corresponds to a choice of where element 1 or 4 sits; each square corresponds to a 2-element set partition.
In parallel coordinates with four axes, each of the 24 permutations becomes a polyline. Because all coordinates sum to 10, every polyline passes through the "mean" height 2.5 if you average its values, but more importantly the structural constraint is that each polyline visits exactly the values , just in a different order. Color a polyline by its number of inversions, its distance from the identity permutation in the weak Bruhat order, and the structure pops out.
Figure 2. The permutohedron of . Left: truncated octahedron (8 hexagons + 6 squares) in 3D, rendered by projecting the 4D points onto the hyperplane. Drag to rotate. Right: all 24 permutations as polylines through 4 axes. Adjacent polylines differ at exactly two consecutive axes (an adjacent transposition). The identity has 3 neighbors; the reverse also has 3 neighbors; each permutation has exactly = 3 neighbors.
Five objects have 120 permutations. The permutohedron of lives in four dimensions: a 4-polytope with 120 vertices, 240 edges, 150 2-faces, and 30 3-faces. The 4D shape cannot be drawn directly, but in 5-axis parallel coordinates all 120 permutations become 120 polylines on the same axes, and the structure of the graph is readable.
Compare the vertex count with the 120-cell, one of the six regular 4-polytopes. Both have 120 vertices. Both live in 4D. But the 120-cell has 720 edges and is highly symmetric under the Coxeter group; the permutohedron of has 240 edges and is symmetric under . They are different polytopes. Parallel coordinates let you put their signatures side by side.
Figure 3. Left: a 2D projection of the 4D permutohedron of , using the eigenvectors of the Coxeter element as projection axes (a classical "Petrie-like" projection). Right: 5-axis parallel coordinates. Toggle to replace the 120 permutations with the 120 120-cell vertices: same axis count, completely different structure. The permutohedron polylines form five bands (values 1 through 5 on each axis); the 120-cell polylines form a continuous fan of golden-ratio-spaced heights.
Same vertex count, different polytope. The 120 vertices of the -permutohedron and the 120 vertices of the 120-cell have nothing combinatorially in common. The permutohedron's graph is 4-regular (each permutation has = 4 neighbors), the 120-cell's graph is 4-regular too, but their face lattices, symmetry groups, and edge lengths are all different. The parallel coordinates view shows this at a glance: integer-valued steps versus a quasi-continuous fan.
The associahedron has five vertices, one for each bracketing of a string of four symbols. The five bracketings are:
Any two bracketings that differ by a single application of the associativity rule are connected by an edge. For example, and differ by one associativity move on the inner (wait, that's two moves; the adjacency in is subtler). The edge structure is exactly Mac Lane's pentagon axiom from category theory: the five bracketings form a pentagon, and walking around the pentagon applies one associativity move at a time.
Equivalently, each vertex is a rooted binary tree with four labeled leaves, and each edge is a single tree rotation. Equivalently again, each vertex is a triangulation of a pentagon by two non-crossing diagonals, and each edge is a single diagonal flip. All three descriptions give the same five-vertex, five-edge polytope: the pentagon.
Figure 4. The associahedron is a pentagon. Its five vertices are the five ways to parenthesize a string of four symbols, equivalently the five binary trees with four labeled leaves, equivalently the five triangulations of a regular pentagon by two non-crossing diagonals. Each edge is a single associativity move / tree rotation / diagonal flip. This is Mac Lane's pentagon axiom from category theory, visible as a polytope.
Five symbols give 14 bracketings, so has 14 vertices. As a 3D polytope it's an enneahedron with 9 facets (6 pentagons and 3 rectangles) and 21 edges. The canonical embedding came from Loday in 2004.
T is a binary tree with n leaves left-to-right. The i-th internal node is the LCA of leaves i and i+1. Li and Ri count its left and right subtree leaves; the product gives one coordinate per internal node. Loday's 2004 paper was three pages long.
For leaves, we get 14 vertices in . Every vertex has integer coordinates. Every vertex's coordinates sum to = 10. The 14 points live in a three-dimensional affine subspace of and form the enneahedron.
Figure 5. Loday's realization of . Left: the 14 vertices projected from onto 3D and connected by 21 edges (tree rotations). Right: all 14 polylines in 4-axis parallel coordinates. The integer coordinates are visible: every polyline sits at integer heights from 1 to 4. The two extreme bracketings are the left-comb with coordinates and the right-comb with coordinates .
The edges of the associahedron are undirected, but there is a natural direction. Orient each rotation so it increases a specific statistic (for example, the number of "right-leaning" internal nodes). The resulting directed graph is the Tamari lattice, a partial order on bracketings. Its unique minimum is the left-comb ; its unique maximum is the right-comb . Every path from bottom to top is a sequence of right rotations that transforms one bracketing into the other.
The Tamari lattice is a poset, so it has a natural drawing: arrange elements by rank (number of right rotations needed from the minimum), with edges connecting cover relations. The Hasse diagram of the Tamari lattice is the 1-skeleton of the associahedron, directed upward.
Figure 6. The Tamari lattice on 14 bracketings of 5 symbols. Left: Hasse diagram with rank increasing upward. The minimum (rank 0) is the left-comb; the maximum (rank 6) is the right-comb. Right: the same 14 polylines as in Figure 5, colored by Tamari rank. The lattice structure is the face lattice of viewed through a direction.
The final picture ties the two polytopes together. There is a natural map from the permutohedron of onto the associahedron, discovered by Jean-Louis Loday and Maria Ronco. Given a permutation = , build a binary tree by placing the largest element at the root, then recursively building the left subtree from the elements appearing before it and the right subtree from those after. The result is a binary tree, hence a vertex of the associahedron. Different permutations may map to the same tree; the fiber over each tree is exactly the set of permutations that are linear extensions of it.
For the permutohedron of with 24 vertices and the associahedron with 5 vertices, this map collapses 24 permutations into 5 clusters. The cluster sizes are = 24. These are the five Catalan compositions of 24, and they give the 24 permutations arranged by their binary-tree structure.
Figure 7. The Loday-Ronco projection. Left: the 24 polylines of the -permutohedron, color-coded by which bracketing of they map to. Right: the pentagon with each vertex sized by the number of permutations in its fiber. The map sends the weak Bruhat order on permutations to the Tamari order on bracketings. Geometrically, it sends the permutohedron onto the associahedron as a polytopal map.
Postnikov's theory puts the permutohedron, associahedron, cyclohedron, and infinitely many others into one family — generalized permutohedra, polytopes obtained by moving permutohedron facets parallel to themselves. The associahedron sits at the opposite end from the permutohedron, and the Loday–Ronco map becomes a projection.
Face lattices: permutohedron ↔ ordered set partitions of [n]; associahedron ↔ non-crossing partitions. Every generalized permutohedron's face lattice sits between these two.
The permutohedron and the associahedron are the first two examples of a much larger zoo: cyclohedra, graph associahedra, nestohedra, hypersimplices. All are generalized permutohedra in Postnikov's sense. All have face lattices that count something combinatorial. The symmetric group acts on the permutohedron by coordinate permutation, making it the type A W-permutohedron in the Coxeter-theoretic classification, the same family that gives the exceptional root systems their own polytopes. The associahedron generalizes to the cluster complex of a finite root system: the type A case gives exactly the Stasheff polytope, but there is also a -associahedron (the cyclohedron), a -associahedron, and exceptional ones for , , .
The associahedron also appears in deep places. Stasheff introduced it in 1963 to define A-infinity spaces, which parameterize spaces with a multiplication that is associative only "up to coherent homotopy." The pentagon axiom in a monoidal category is just the 2-cells of ; the higher associativity coherences are cells of , , and so on. The associahedron is the combinatorial shape of associativity itself.
The permutohedron has its own deep connections: tropical geometry (it is the Bergman fan of a matroid), hyperplane arrangements (its normal fan is the braid arrangement), and the theory of Newton polytopes for symmetric functions. When you visualize these polytopes in parallel coordinates, you are seeing the shadows of the combinatorics that generate them. The crossings tell you which permutations or bracketings are adjacent. The bundles tell you which symmetry groups are acting. The fibers of the projection tell you how the two worlds are glued together.
A 120-vertex polytope in 4D could be the 120-cell, or it could be the permutohedron of . They share a vertex count but nothing else. In parallel coordinates, you can tell them apart at a glance.