permutohedron

According to {{harvs|txt|last=Ziegler|first=Günter M.|authorlink=Günter M. Ziegler|year=1995}}, permutohedra were first studied by {{harvs|txt|first=Pieter Hendrik|last=Schoute|authorlink=Pieter Hendrik Schoute|year=1911}}. The name permutoèdre was coined by {{harvs|txt|first1=Georges Th.|last1=Guilbaud|first2=Pierre|last2=Rosenstiehl|authorlink2=Pierre Rosenstiehl|year=1963}}. They describe the word as barbaric, but easy to remember, and 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.{{harvtxt|Thomas|2006}}. Permutohedra are sometimes called permutation polytopes, but this terminology is also used for the related Birkhoff polytope, defined as the convex hull of permutation matrices. More generally, {{harvs|txt|last=Bowman|first=V. Joseph|year=1972}} uses that term for any polytope whose vertices have a bijection with the permutations of some set.

The permutohedron of order {{math|n}} has {{math|n!}} vertices, each of which is adjacent to {{math|n − 1}} others.

The number of edges is {{math|{{sfrac|(n − 1) n!|2}}}}, and their length is {{math|square root of 2}}.

Two connected vertices differ by swapping two coordinates, whose values differ by 1.{{harvtxt|Gaiha|Gupta|1977}}. The pair of swapped places corresponds to the direction of the edge.

(In the example image the vertices {{math|(3, 2, 1, 4)}} and {{math|(2, 3, 1, 4)}} are connected by a blue edge and differ by swapping 2 and 3 on the first two places. The values 2 and 3 differ by 1. All blue edges correspond to swaps of coordinates on the first two places.)

The number of facets is {{math|2ⁿ − 2}}, because they correspond to non-empty proper subsets {{math|S}} of {{math|{{mset|1 ... n}}}}.

The vertices of a facet corresponding to subset {{math|S}} have in common, that their coordinates on places in {{math|S}} are smaller than the rest.{{harvtxt|Lancia|2018}}, p. 105 (see chapter [https://www.mimuw.edu.pl/~jarekw/pdf/Permutahedron.pdf The Permutahedron]).

More generally, the faces of dimensions 0 (vertices) to {{math|n − 1}} (the permutohedron itself) correspond to the strict weak orderings of the set {{math|{{mset|1 ... n}}}}. So the number of all faces is the {{math|n}}-th ordered Bell number.See, e.g., {{harvtxt|Ziegler|1995}}, p. 18.

A face of dimension {{math|d}} corresponds to an ordering with {{math|k {{=}} n − d}} equivalence classes.

|}

The number of faces of dimension {{math|d {{=}} n − k}} in the permutohedron of order {{math|n}} is given by the triangle {{math|T}} {{OEIS|A019538}}:

$$T(n,k)\; =\; k!\; \backslash cdot\; \backslash left\backslash \{\{n\backslash atop\; k\}\backslash right\backslash \}$$

with $\backslash textstyle\; \backslash left\backslash \{\{n\backslash atop\; k\}\backslash right\backslash \}$ representing the Stirling numbers of the second kind.

It is shown on the right together with its row sums, the ordered Bell numbers.

File:Symmetric group 4; Cayley graph 1,2,6 (1-based).png for a comparison with the permutohedron)]]

The permutohedron is vertex-transitive: the symmetric group {{math|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 {{math|n(n − 1)/2}} line segments that connect the pairs of the standard basis vectors.{{sfnp|Ziegler|1995|p=200}}

The vertices and edges of the permutohedron are isomorphic to one of the Cayley graphs of the symmetric group, namely the one generated by the transpositions that swap consecutive elements. The vertices of the Cayley graph are the inverse permutations of those in the permutohedron.This Cayley graph labeling is shown, e.g., by {{harvtxt|Ziegler|1995}}. The image on the right shows the Cayley graph of {{math|S4}}. Its edge colors represent the 3 generating transpositions: {{color|blue|(1, 2)}}, {{color|green|(2, 3)}}, {{color|red|(3, 4)}}.

This Cayley graph is Hamiltonian; a Hamiltonian cycle may be found by the Steinhaus–Johnson–Trotter algorithm.

{{multiple image

| align = right | total_width = 310

| image1 = Hexagonal tiling.svg

| image2 = Bitruncated cubic honeycomb.png

| footer = Tesselation of space by permutohedra of orders 3 and 4

}}

The permutohedron of order {{mvar|n}} lies entirely in the {{math|(n − 1)}}-dimensional hyperplane consisting of all points whose coordinates sum to the number:

$$1\; +\; 2\; +\; \backslash ldots\; +\; n\; =\; \backslash frac\{n(n+1)\}\{2\}$$

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

$$\backslash begin\{align\}$$

& x_1 + x_2 + \ldots + x_n = 0 \\

& x_1 \equiv x_2 \equiv \ldots \equiv x_n \pmod n.

\end{align}

This is the lattice $A\_\{n-1\}^*$, the dual lattice of the root lattice $A\_\{n-1\}$. In other words, the permutohedron is the Voronoi cell for $A\_\{n-1\}^*$. Accordingly, this lattice is sometimes called the permutohedral lattice.{{sfnp|Baek|Adams|Dolson|2013}}

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 {{tmath|\R^4}} with coordinates {{math|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),\backslash \; (1,1,-3,1),\backslash \; (1,-3,1,1),\backslash \; (-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. The dual tessellations contain all simplex facets, although they are not regular polytopes beyond order-3.

{{Commons category|Permutohedra}}

• Associahedron
• Cyclohedron
• Permutoassociahedron

{{reflist}}

• {{citation|last1=Baek|first1=Jongmin|last2=Adams|first2=Andrew|last3=Dolson|first3=Jennifer|doi=10.1007/s10851-012-0379-2|issue=2|journal=Journal of Mathematical Imaging and Vision|mr=3061550|pages=211–237|title=Lattice-based high-dimensional Gaussian filtering and the permutohedral lattice|volume=46|year=2013|hdl=1721.1/105344|hdl-access=free}}
• {{citation|first=V. Joseph|last=Bowman|title=Permutation polyhedra|journal=SIAM Journal on Applied Mathematics|volume=22|issue=4|pages=580–589| year=1972| doi=10.1137/0122054|jstor=2099695|mr=0305800}}.
• {{citation|first1=Prabha|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|doi=10.1137/0132025|jstor=2100417|mr=0427102}}.
• {{citation|first1=Georges Th.|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/item?id=MSH_1963__4__9_0}}.
• {{citation| last = Lancia | first = Giuseppe | title = Compact extended linear programming models | publisher = Springer | location = Cham, Switzerland | year = 2018 | isbn = 978-3-319-63975-8}}.
• {{citation|first=Pieter Hendrik|last=Schoute|author-link=Pieter Hendrik 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}} [https://books.google.com/books?id=qC5LAAAAYAAJ&dq=Analytic+treatment+of+the+polytopes+regularly+derived+from+the+regular+polytopes&pg=PA357 Googlebook, 370–381] Also online on the KNAW Digital Library at http://www.dwc.knaw.nl/toegangen/digital-library-knaw/?pagetype=publDetail&pId=PU00011495
• {{citation|title=Lectures in Geometric Combinatorics|title-link= Lectures in Geometric Combinatorics |volume=33|series=Student Mathematical Library: IAS/Park City Mathematical Subseries|first=Rekha R.|last=Thomas|author-link=Rekha R. Thomas|publisher=American Mathematical Society|year=2006|isbn=978-0-8218-4140-2|contribution=Chapter 9. The Permutahedron|pages=85–92}}.
• {{citation|first=Günter M.|last=Ziegler|author-link=Günter M. Ziegler|title=Lectures on Polytopes|publisher=Springer-Verlag, Graduate Texts in Mathematics 152|year=1995}}.

• {{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|ref=none}}.
• {{citation|last=Postnikov|first=Alexander|arxiv=math.CO/0507163|doi=10.1093/imrn/rnn153|issue=6|journal=International Mathematics Research Notices|mr=2487491|pages=1026–1106|title=Permutohedra, associahedra, and beyond|year=2009|volume=2009 }}
• {{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|ref=none|doi=10.1080/0025570X.2007.11953465}}

• {{mathworld|title=Permutohedron|urlname=Permutohedron|author=Bryan Jacobs|mode=cs2}}

Category:Permutations

Category:Polytopes