Permutaeder

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

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

${\displaystyle 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.

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

${\displaystyle 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 ${\displaystyle P_{n}}$ liegt in der ${\displaystyle (n-1)}$-dimensionalen Hyperebene

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

Die Hyperebene ${\displaystyle H}$ besteht gerade aus den Punkten, deren Koordinatensumme ${\displaystyle {\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 ${\displaystyle (n-1)}$-dimensionale Gitter:

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

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

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