World Library  
Flag as Inappropriate
Email this Article

Permutohedron

Article Id: WHEBN0012745947
Reproduction Date:

Title: Permutohedron  
Author: World Heritage Encyclopedia
Language: English
Subject: Inversion (discrete mathematics), Geometric combinatorics, Lovász conjecture, Schröder–Hipparchus number, List of permutation topics
Collection: Permutations, Polytopes
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Permutohedron

The permutohedron of order 4

In mathematics, the permutohedron of order n (also spelled permutahedron)[1] 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).

Contents

  • History 1
  • Vertices, edges, and facets 2
  • Other properties 3
  • Tessellation of the space 4
  • Gallery 5
  • See also 6
  • Notes 7
  • References 8
  • External links 9

History

According to Ziegler (1995), permutohedra were first studied by Schoute (1911). The name "permutohedron" (or rather its French version, "permutoèdre") was coined by 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.[2]

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, Bowman (1972) uses the phrase "permutation polytope" for any polytope whose vertices are in 1-1 correspondence with the permutations of some set.

Vertices, edges, and facets

The 13 weak orderings on (or ordered partitions of) the set {1,2,3} in the permutohedron-like Cayley graph of S3
   k = 1    2    3    4    5
n
1      1                               1
2      1    2                          3
3      1    6    6                    13
4      1   14   36   24               75
5      1   30  150  240  120         541

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.[3]

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 2n − 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. Because of this correspondence, the number of faces is given by the ordered Bell numbers.[4]

The number of (nk)-dimensional faces in a permutohedron of order n is found in the triangle T(n,k) = k! * Stirling2(n,k) (sequence A019538 in OEIS) - shown on the right, together with its row sums, the ordered Bell numbers.

Other properties

Cayley graph of S4, generated by the 3 adjacent transpositions of 4 elements
Only self-inverse permutations are at the same positions as in the permutohedron; the others are replaced by their inverses.

The permutohedron is vertex-transitive: the symmetric group Sn 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 .[5]

The vertices and edges of the permutohedron are isomorphic as an undirected graph to one of the Cayley graphs of the symmetric group: The Cayley graph generated by the adjacent transpositions in the symmetric group (transpositions that swap consecutive elements). The Cayley graph of S4, shown on the right, is generated by the transpositions (1,2), (2,3), and (3,4).
The Cayley graph labeling can be constructed by labeling each vertex by the inverse of the permutation given by its coordinates.[6]

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

Tessellation of the space

Tesselation of space by permutohedra

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 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:

x1 + x2 + … + xn = 0,     x1x2 ≡ … ≡ xn (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 R4 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. The dual tessellations contain all simplex facets, although they are not regular polytopes beyond order-3.

Gallery

Order 2 Order 3 Order 4
2 vertices 6 vertices 24 vertices
The permutohedron of order 2 is a line segment on the diagonal of a unit square. The permutohedron of order 3 is a regular hexagon, filling a cross-section of a 2×2×2 cube. The permutohedron of order 4 forms a truncated octahedron.
Order 5 Order 6
120 vertices 720 vertices
The permutohedron of order 5 forms an omnitruncated 5-cell. The permutohedron of order 6 forms an omnitruncated 5-simplex.

See also

Notes

  1. ^ Rekha (2006).
  2. ^ Original French: "le mot permutoèdre est barbare, mais il est facile à retenir; soumettons le aux critiques des lecteurs."
  3. ^ Gaiha & Gupta (1977).
  4. ^ See, e.g., Ziegler (1995), p. 18.
  5. ^ Ziegler (1995), p. 200.
  6. ^ This Cayley graph labeling is shown, e.g., by Ziegler (1995).

References

  • Bowman, V. J. (1972), "Permutation polyhedra", SIAM Journal on Applied Mathematics 22 (4): 580–589,  .
  • Gaiha, P.; Gupta, S. K. (1977), "Adjacent vertices on a permutohedron", SIAM Journal on Applied Mathematics 32 (2): 323–327,  .
  • Guilbaud, G. Th.;  .
  • Le Conte de Poly-Barbut, Cl. (1990), "Le diagramme du treillis permutoèdre est intersection des diagrammes de deux produits directs d’ordres totaux", Mathématiques, Informatique et Sciences Humaines 112: 49–53 .
  • Santmyer, Joe (2007), "For all possible distances look to the permutohedron",  
  •   Googlebook, 370–381
  • Thomas, Rekha R. (2006), "Chapter 9. The Permutahedron", Lectures in Geometric Combinatorics, Student Mathematical Library: IAS/Park City Mathematical Subseries 33, American Mathematical Society, pp. 85–92,  .
  •  

External links

  • Bryan Jacobs, "Permutohedron", MathWorld.
  • Alexander Postnikov (2005). "Permutohedra, associahedra, and beyond". arXiv:math.CO/0507163 [math.CO].
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.