In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the permutohedron of order ''n'' is an (''n'' − 1)-dimensional
polytope
In elementary geometry, a polytope is a geometric object with flat sides (''faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an -d ...
embedded in an ''n''-dimensional space. Its
vertex
Vertex, vertices or vertexes may refer to:
Science and technology Mathematics and computer science
*Vertex (geometry), a point where two or more curves, lines, or edges meet
* Vertex (computer graphics), a data structure that describes the positio ...
coordinates (labels) are the
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
s of the first ''n''
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s. The edges identify the shortest possible paths (sets of
transpositions) that connect two vertices (permutations). Two permutations connected by an edge differ in only two places (one
transposition), and the numbers on these places are neighbors (differ in value by 1).
The image on the right shows the permutohedron of order 4, which is the
truncated octahedron
In geometry, the truncated octahedron is the Archimedean solid that arises from a regular octahedron by removing six pyramids, one at each of the octahedron's vertices. The truncated octahedron has 14 faces (8 regular hexagon, hexagons and 6 Squa ...
. Its vertices are the 24 permutations of (1, 2, 3, 4). Parallel edges have the same edge color. The 6 edge colors correspond to the 6 possible
transpositions of 4 elements, i.e. they indicate in which two places the connected permutations differ. (E.g. red edges connect permutations that differ in the last two places.)
History
According to , permutohedra were first studied by . The name ''permutoèdre'' was coined by . They describe the word as barbaric, but easy to remember, and submit it to the criticism of their readers.
The alternative spelling ''permutahedron'' is sometimes also used. Permutohedra are sometimes called ''permutation polytopes'', but this terminology is also used for the related
Birkhoff polytope
The Birkhoff polytope ''B'n'' (also called the assignment polytope, the polytope of doubly stochastic matrices, or the perfect matching polytope of the complete bipartite graph K_) is the convex polytope in R''N'' (where ''N'' = ''n''2) who ...
, defined as the convex hull of
permutation matrices
In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix, say , represents a permutation of elements and, when ...
. More generally, uses that term for any polytope whose vertices have a
bijection
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
with the permutations of some set.
Vertices, edges, and facets
The permutohedron of order has vertices, each of which is adjacent to others.
The number of edges is , and their length is .
Two connected vertices differ by swapping two coordinates, whose values differ by 1. The pair of swapped places corresponds to the direction of the edge.
(In
the example image the vertices and 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
A facet is a flat surface of a geometric shape, e.g., of a cut gemstone.
Facet may also refer to:
Arts, entertainment, and media
* ''Facets'' (album), an album by Jim Croce
* ''Facets'', a 1980 album by jazz pianist Monty Alexander and his tri ...
is , because they correspond to non-empty proper
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
s of .
The vertices of a facet corresponding to subset have in common, that their coordinates on places in are smaller than
the rest.
More generally, the
faces
The face is the front of an animal's head that features the eyes, nose and mouth, and through which animals express many of their emotions. The face is crucial for human identity, and damage such as scarring or developmental deformities may affe ...
of dimensions 0 (vertices) to (the permutohedron itself) correspond to the
strict weak orderings of the set . So the number of all faces is the -th
ordered Bell number
In number theory and enumerative combinatorics, the ordered Bell numbers or Fubini numbers count the number of weak orderings on a set of ''n'' elements (orderings of the elements into a sequence allowing ties, such as might arise as the outcome ...
.
[See, e.g., , p. 18.]
A face of dimension corresponds to an ordering with equivalence classes.
The number of faces of dimension in the permutohedron of order is given by the triangle :
with
representing the
Stirling numbers of the second kind
In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of ''n'' objects into ''k'' non-empty subsets and is denoted by S(n,k) or \textstyle \lef ...
It is shown on the right together with its row sums, the
ordered Bell number
In number theory and enumerative combinatorics, the ordered Bell numbers or Fubini numbers count the number of weak orderings on a set of ''n'' elements (orderings of the elements into a sequence allowing ties, such as might arise as the outcome ...
s.
Other properties
The permutohedron is
vertex-transitive
In geometry, a polytope (e.g. a polygon or polyhedron) or a tiling is isogonal or vertex-transitive if all its vertices are equivalent under the symmetries of the figure. This implies that each vertex is surrounded by the same kinds of face in ...
: the
symmetric group
In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group \m ...
S
''n'' acts
The Acts of the Apostles ( grc-koi, Πράξεις Ἀποστόλων, ''Práxeis Apostólōn''; la, Actūs Apostolōrum) is the fifth book of the New Testament; it tells of the founding of the Christian Church and the spread of its message ...
on the permutohedron by permutation of coordinates.
The permutohedron is a
zonotope
In geometry, a zonohedron is a convex polyhedron that is centrally symmetric, every face of which is a polygon that is centrally symmetric (a zonogon). Any zonohedron may equivalently be described as the Minkowski sum of a set of line segments in ...
; a translated copy of the permutohedron can be generated as the
Minkowski sum
In geometry, the Minkowski sum (also known as dilation) of two sets of position vectors ''A'' and ''B'' in Euclidean space is formed by adding each vector in ''A'' to each vector in ''B'', i.e., the set
: A + B = \.
Analogously, the Minkowski ...
of the
''n''(''n'' − 1)/2 line segments that connect the pairs of the
standard basis
In mathematics, the standard basis (also called natural basis or canonical basis) of a coordinate vector space (such as \mathbb^n or \mathbb^n) is the set of vectors whose components are all zero, except one that equals 1. For example, in the c ...
vectors.
The vertices and edges of the permutohedron are
isomorphic
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
to one of the
Cayley graph
In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cay ...
s of the
symmetric group
In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group \m ...
, 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 .] The image on the right shows the Cayley graph of S
4. Its edge colors represent the 3 generating transpositions: , ,
This Cayley graph is
Hamiltonian
Hamiltonian may refer to:
* Hamiltonian mechanics, a function that represents the total energy of a system
* Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system
** Dyall Hamiltonian, a modified Hamiltonian ...
; a Hamiltonian cycle may be found by the
Steinhaus–Johnson–Trotter algorithm
The Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all of the permutations of n elements. ...
.
Tessellation of the space
The permutohedron of order ''n'' lies entirely in the ()-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 infinitely many
translated
Translation is the communication of the meaning of a source-language text by means of an equivalent target-language text. The English language draws a terminological distinction (which does not exist in every language) between ''transla ...
copies of the permutohedron. Each of them differs from the basic permutohedron by an element of a certain (''n'' − 1)-dimensional
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
, which consists of the ''n''-tuples of integers that sum to zero and whose
residues (modulo ''n'') are all equal:
: ''x''
1 + ''x''
2 + ... + ''x''
''n'' = 0
: ''x''
1 ≡ ''x''
2 ≡ ... ≡ ''x''
''n'' (mod ''n'').
This is the lattice
, the
dual lattice
In the theory of lattices, the dual lattice is a construction analogous to that of a dual vector space. In certain respects, the geometry of the dual lattice of a lattice L is the reciprocal of the geometry of L , a perspective which underlie ...
of the
root lattice . In other words, the permutohedron is the
Voronoi cell
In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed t ...
for
. Accordingly, this lattice is sometimes called the permutohedral lattice.
Thus, the permutohedron of order 4 shown above tiles the 3-dimensional space by translation. Here the 3-dimensional space is the
affine subspace
In mathematics, an affine space is a geometric structure that generalizes some of the properties of Euclidean spaces in such a way that these are independent of the concepts of distance and measure of angles, keeping only the properties related ...
of the 4-dimensional space R
4 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
In geometry, an apeirogon () or infinite polygon is a generalized polygon with a countably infinite number of sides. Apeirogons are the two-dimensional case of infinite polytopes.
In some literature, the term "apeirogon" may refer only to the ...
, the regular
hexagonal tiling, and the
bitruncated cubic honeycomb
The bitruncated cubic honeycomb is a space-filling tessellation (or honeycomb) in Euclidean 3-space made up of truncated octahedra (or, equivalently, bitruncated cubes). It has 4 truncated octahedra around each vertex. Being composed entirely of t ...
. The dual tessellations contain all
simplex
In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...
facets, although they are not regular polytopes beyond order-3.
Examples
See also
*
Associahedron
In mathematics, an associahedron is an -dimensional convex polytope in which each vertex corresponds to a way of correctly inserting opening and closing parentheses in a string of letters, and the edges correspond to single application of ...
*
Cyclohedron
In geometry, the cyclohedron is a d-dimensional polytope where d can be any non-negative integer. It was first introduced as a combinatorial object by Raoul Bott and Clifford Taubes and, for this reason, it is also sometimes called the Bott–Taube ...
*
Permutoassociahedron
In mathematics, the permutoassociahedron is an n-dimensional polytope whose vertices correspond to the bracketings of the permutations of n+1 terms and whose edges connect two bracketings that can be obtained from one another either by moving a p ...
Notes
References
*
*.
*.
*.
* .
Googlebook, 370–381Also online on the KNAW Digital Library at http://www.dwc.knaw.nl/toegangen/digital-library-knaw/?pagetype=publDetail&pId=PU00011495
*.
*.
Further reading
*.
*
*
External links
*{{mathworld, title=Permutohedron, urlname=Permutohedron, author=Bryan Jacobs, mode=cs2
Permutations
Polytopes