Permutaeder

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Der Permutaeder P_4

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

Definition[Bearbeiten]

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[Bearbeiten]

Tesselation des Raumes durch Permutaeder

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[Bearbeiten]

Weblinks[Bearbeiten]