Permutohedron

In mathematics, the permutohedron of order "n" is an ("n" − 1)-dimensional polytope embedded in an "n"-dimensional space, the vertices of which are formed by permuting the coordinates of the vector (1, 2, 3, ..., "n").

Examples

* Order 1: A single point: (1)
* Order 2: A line segment on the plane: (1,2), (2,1).
* Order 3: A regular hexagon with vertices defined as the six permutations of (1, 2, 3) in the plane "x" + "y" + "z" = 6.
* Order 4: A uniform truncated octahedron with vertices as the 24 permutations of (1, 2, 3, 4), in the three-dimensional subspace "x" + "y" + "z" + "w" = 10.
* Order 5: A uniform omnitruncated 5-cell, with 120 vertices as the permutations of (1,2,3,4,5).

Vertices, edges, and facets

The permutohedron of order "n" has "n"! vertices, each of which is adjacent to "n" − 1 others, so the total number of edges is ("n" − 1)"n"!/2. Each edge has length √2, and connects two vertices that differ by swapping two coordinates the values of which differ by one. [harvtxt|Gaiha|Gupta|1977.]

The permutohedron has one facet for each nonempty proper subset "S" of {1, 2, 3, ..., "n"}, consisting of the vertices in which all coordinates in positions in "S" are smaller than all coordinates in positions not in "S". Thus, the total number of facets is 2^"n" − 2.More generally, the faces of the permutohedron (including the permutohedron itself, but not including the empty set) are in 1-1 correspondence with the strict weak orderings on a set of "n" items: a face of dimension "d" corresponds to a strict weak ordering in which there are "n" − "d" equivalence classes.See, e.g., harvtxt|Ziegler|1995, p. 18.]

pace-filling tessellation

The permutohedron of order "n" lies entirely in the ("n" − 1)-dimensional hyperplane consisting of all points whose coordinates sum to the number

: 1 + 2 + … + "n" = "n"("n" + 1)/2.

Moreover, this hyperplane can be tiled by the infinitely many translated copies of the permutohedron. Each of them differs from the basic permutohedron by an element of a certain ("n" − 1)-dimensional lattice, which consists of the "n"-tuples of integers that sum to zero and whose residues (modulo "n") are all equal:

: "x"₁ + "x"₂ + … + "x"_"n" = 0,     "x"₁ ≡ "x"₂ ≡ … ≡ "x"_"n" (mod "n").

Thus, the permutohedron of order 4 shown above tiles the 3-dimensional space by translation. Here the 3-dimensional space is the affine subspace of the 4-dimensional space R⁴ with coordinates "x", "y", "z", "w" that consists of the 4-tuples of real numbers whose sum is 10,

: "x" + "y" + "z" + "w" = 10.

One easily checks that for each of the following four vectors,

: (1,1,1,−3), (1,1,−3,1), (1,−3,1,1) and (−3,1,1,1),

the sum of the coordinates is zero and all coordinates are congruent to 1 (mod 4). Any three of these vectors generate the translation lattice.

The tessellations formed in this way from the order-2, order-3, and order-4 permutohedra, respectively, are the apeirogon, the regular hexagonal tiling, and the bitruncated cubic honeycomb.

Other properties

The permutohedron is vertex-transitive: the symmetric group "S_n" acts on the permutohedron by permutation of coordinates.

The permutohedron is a zonotope; a translated copy of the permutohedron can be generated as the Minkowski sum of the "n"("n" − 1)/2 line segments that connect the pairs of the standard basis vectors . [harvtxt|Ziegler|1995, p. 200.]

The vertices and edges of the permutohedron are isomorphic as a graph to a Cayley graph for the symmetric group, having as its generators the permutations that swap adjacent pairs of items. The Cayley graph labeling can be constructed by labeling each vertex by the inverse of the permutation given by its coordinates. [This Cayley graph labeling is shown, e.g., by harvtxt|Ziegler|1995.]

History

According to harvtxt|Ziegler|1995, permutohedra were first studied by harvtxt|Schoute|1911. The name "permutohedron" (or rather its French version, "permutoèdre") was coined by harvtxt|Guibaud|Rosenstiehl|1963. Regarding this coinage, they write that the word "permutohedron" is barbaric, but easy to remember, and that they submit it to the criticism of their readers. [Original French: "le mot permutoèdre est barbare, mais il est facile à retenir; soumettons le aux critiques des lecteurs."]

The alternative spelling permutahedron is sometimes also used. Permutohedra are sometimes also called permutation polytopes, but this terminology is also used for a related polytope, the Birkhoff polytope, defined as the convex hull of permutation matrices. More generally, harvtxt|Bowman|1972 uses the phrase "permutation polytope" for any polytope whose vertices are in 1-1 correspondence with the permutations of some set.

See also

* Associahedron

Notes

References

*citation|first=V. J.|last=Bowman|title=Permutation polyhedra|journal=SIAM Journal on Applied Mathematics|volume=22|issue=4|pages=580–589|year=1972|url=http://links.jstor.org/sici?sici=0036-1399(197206)22%3A4%3C580%3APP%3E2.0.CO%3B2-P.

*citation|first1=P.|last1=Gaiha|first2=S. K.|last2=Gupta|title=Adjacent vertices on a permutohedron|journal=SIAM Journal on Applied Mathematics|volume=32|issue=2|pages=323–327|year=1977|url=http://links.jstor.org/sici?sici=0036-1399(197703)32%3A2%3C323%3AAVOAP%3E2.0.CO%3B2-1.

*citation|first1=Georges-théodule|last1=Guilbaud|first2=Pierre|last2=Rosenstiehl|authorlink2=Pierre Rosenstiehl|title=Analyse algébrique d'un scrutin|journal=Mathématiques et sciences humaines|volume=4|year=1963|pages=9–33|url=http://www.numdam.org/numdam-bin/fitem?ma=189547&id=MSH_1963__4__9_0.

*citation|first=Cl.|last=Le Conte de Poly-Barbut|title=Le diagramme du treillis permutoèdre est intersection des diagrammes de deux produits directs d’ordres totaux|journal=Mathématiques, Informatique et Sciences Humaines|volume=112|pages=49–53|year=1990.

*citation|first=Joe|last=Santmyer|title=For all possible distances look to the permutohedron|journal=Mathematics Magazine|volume=80|issue=2|year=2007|pages=120–125|url=http://www.ingentaconnect.com/content/maa/mm/2007/00000080/00000002/art00005

*citation|first=Pieter Hendrik|last=Schoute|title=Analytic treatment of the polytopes regularly derived from the regular polytopes|journal=Verhandelingen der Koninklijke Akademie van Wetenschappen te Amsterdam|volume=11|issue=3|year=1911|pages=87 pp.

*citation|first=Günter M.|last=Ziegler|authorlink=Günter M. Ziegler|title=Lectures on Polytopes|publisher=Springer-Verlag, Graduate Texts in Mathematics 152|year=1995

External links

*mathworld|title=Permutohedron|urlname=Permutohedron|author=Bryan Jacobs
* [http://www.math.ubc.ca/~holroyd/cayley/s5.html Rotatable order-5 permutohedron]
*