Permutahedron & Associahedron Permutaeder & Assozieder
Two important polytopes from algebraic combinatorics Zwei wichtige Polytope der algebraischen Kombinatorik
The permutahedron and the associahedron are two of the most important polytopes in algebraic combinatorics. Our exhibit shows 3D models of both, printed as the permutahedron (in yellow) inside the one-skeleton of the associahedron (in black), with a smaller associahedron sitting behind (in orange).
The permutahedron $(n-1)$-dimensional polytope inside $\mathbb R^n$ whose vertices are all permutations of the coordinates $(1, 2, \ldots, n)$. For $n = 4$, it is the well-known truncated octahedron — a $3$-dimensional polytope with 24 vertices, 36 edges, and 14 faces (6 squares and 8 hexagons).
The associahedron is a polytope whose vertices correspond to the triangulations of a convex polygon and whose edges correspond to diagonal flips. In dimension 3, it is a polytope with 14 vertices, 21 edges, and 9 faces (3 quadrilaterals and 6 pentagons).
| Property | Permutahedron | Associahedron |
|---|---|---|
| Dimension | $n$ | $n$ |
| Vertices | $(n+1)!$ | $C_{n+1}$ |
| Facets | $2^{n+1} - 2$ | $\tfrac{n(n+3)}{2}$ |
Here, $C_k = \tfrac{1}{k+1}\binom{2k}{k}$ denotes the $k$-th Catalan number. Both polytopes are simple, meaning that every vertex is adjacent to exactly $n$ edges.
From Permutahedron to Associahedron
As indicated in the 3D model, the associahedron can be obtained from the permutahedron by removing certain facets. More precisely, the normal fan of the associahedron is a coarsening of the normal fan of the permutahedron.
Further Reading
Das Permutaeder und das Assozieder sind zwei der bedeutendsten Polytope der algebraischen Kombinatorik. Unsere Ausstellung zeigt 3D-Modelle beider Polytope: das Permutaeder (in Gelb) innerhalb des Einsskeletts des Assozieders (in Schwarz), mit einem kleineren Assozieder dahinter (in Orange).
Das Permutaeder der Ordnung $n$ ist ein $(n-1)$-dimensionales Polytop, dessen Ecken alle Permutationen der Koordinaten $(1, 2, \ldots, n)$ sind. Für $n = 4$ ist es das bekannte abgestumpfte Oktaeder — ein 3-dimensionales Polytop mit 24 Ecken, 36 Kanten und 14 Flächen (6 Quadrate und 8 Sechsecke).
Das Assozieder ist ein Polytop, dessen Ecken den Triangulierungen eines konvexen Polygons entsprechen und dessen Kanten Diagonalflips entsprechen. In Dimension 3 ist es ein Polytop mit 14 Ecken, 21 Kanten und 9 Flächen (3 Vierecke und 6 Fünfecke).
| Eigenschaft | Permutaeder | Assozieder |
|---|---|---|
| Dimension | $n$ | $n$ |
| Ecken | $(n+1)!$ | $C_{n+1}$ |
| Facetten | $2^{n+1} - 2$ | $\tfrac{n(n+3)}{2}$ |
Dabei bezeichnet $C_k = \tfrac{1}{k+1}\binom{2k}{k}$ die $k$-te Catalansche Zahl. Beide Polytope sind einfach, das heißt, jede Ecke liegt auf genau $n$ Kanten.
Vom Permutaeder zum Assozieder
Wie im 3D-Modell angedeutet, kann das Assozieder aus dem Permutaeder durch Entfernen bestimmter Facetten gewonnen werden. Genauer gesagt ist der Normalenfächer des Assozieders eine Vergröberung des Normalenfächers des Permutaeders.
Weiterführende Literatur