Permutahedron

The permutahedron ${\displaystyle P_{4}}$

In mathematics, a permutahedron is a convex polytope (generalized polygon) in dimensional space, the corners of which are created by the permutations of the coordinates of the vector . ${\displaystyle n}$ ${\displaystyle (1,2,3,\ldots ,n)}$

definition

The permutahedron of the order is a convex polytope which is defined as follows: Each permutation of the symmetric group is interpreted in tuple notation as a vector im . The convex hull of these vectors then gives : ${\displaystyle P_{n}}$ ${\displaystyle n}$ ${\displaystyle \sigma }$ ${\displaystyle S_{n}}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle P_{n}}$

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

The corners of the permutahedron are precisely the permutations in tuple notation. Two permutations are connected by an edge of the permutahedron if they can be converted into one another by transposing neighboring elements.

properties

Tessellation of space by permutahedron ( truncated octahedra )

The permutahedron can also be described by the intersection of half-spaces :

${\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\}}$

The permutahedron lies in the -dimensional hyperplane ${\displaystyle P_{n}}$ ${\displaystyle (n-1)}$

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

The hyperplane consists of the points whose coordinate sum is. It has a tessellation through an infinite number of parallel shifted copies of the permutahedron. The symmetry group of this tessellation is the -dimensional lattice given by the following equations : ${\displaystyle H}$ ${\displaystyle {\tbinom {n+1}{2}}={\tfrac {n(n+1)}{2}}}$ ${\displaystyle (n-1)}$

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

literature

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

Web links

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