Permutaeder

Der Permutaeder $P_{4}$

Ein Permutaeder ist in der Mathematik ein konvexes Polytop (verallgemeinertes Vieleck) im $n$-dimensionalen Raum, dessen Ecken durch die Permutationen der Koordinaten des Vektors $(1,2,3,\ldots ,n)$ entstehen.

Definition

Der Permutaeder $P_{n}$ der Ordnung $n$ ist ein konvexes Polytop, das wie folgt definiert ist: Jede Permutation $\sigma$ der symmetrischen Gruppe $S_{n}$ wird in Tupelschreibweise geschrieben als Vektor im $\mathbb {R} ^{n}$ interpretiert. Die konvexe Hülle dieser Vektoren ergibt dann $P_{n}$:

$P_{n}:=\operatorname {conv} \left\{\sigma =(\sigma (1),\sigma (2),\ldots ,\sigma (n))\mid \sigma \in S_{n}\right\}$

Die Ecken des Permutaeders sind gerade die Permutationen in Tupelschreibweise. Zwei Permutationen sind dabei genau dann durch eine Kante des Permutaeders verbunden, wenn sie sich durch eine Transposition benachbarter Elemente ineinander überführen lassen.

Eigenschaften

Tesselation des Raumes durch Permutaeder (Oktaederstümpfe)

Der Permutaeder lässt sich auch durch den Schnitt von Halbräumen beschreiben:

$P_{n}=\left\{x\in \mathbb {R} ^{n}\mid \sum _{i=1}^{n}x_{i}={n+1 \choose 2},\;\forall S\subset \{1,\ldots ,n\}:\sum _{i\in S}x_{i}\geq {|S|+1 \choose 2}\right\}$

Der Permutaeder $P_{n}$ liegt in der $(n-1)$-dimensionalen Hyperebene

$H=\left\{x\in \mathbb {R} ^{n}\mid x_{1}+x_{2}+\ldots +x_{n}={n+1 \choose 2}\right\}$

Die Hyperebene $H$ besteht gerade aus den Punkten, deren Koordinatensumme ${\tbinom {n+1}{2}}={\tfrac {n(n+1)}{2}}$ ist. Sie hat eine Tessellation durch unendlich viele parallelverschobene Kopien des Permutaeders. Die Symmetriegruppe dieser Tesselation ist das durch die folgenden Gleichungen gegebene $(n-1)$-dimensionale Gitter:

$x_{1}+x_{2}+\ldots +x_{n}=0,\;x_{1}\equiv x_{2}\equiv \ldots x_{n}\mod n$

Literatur

• Günter M. Ziegler: Lectures on Polytopes (= Graduate Texts in Mathematics. Band 152). Springer-Verlag, 1995, ISBN 0-387-94365-X. 

Weblinks

• Bryan Jacobs: Permutohedron. In: MathWorld (englisch).