A fact from Permutohedron appeared on Wikipedia's
Main Page in the
Did you know column on 17 August 2007. The text of the entry was as follows:
|
This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
The article claims that every permutohedron is a zonotope. This is morally true, but unfortunately a zonotope is defined to be a 3-dimensional thing, while a permutohedron can be n-dimensional for any n. This can't be fixed in the permutohedron article, it needs to be fixed in the zonotope article. Adam1729 01:16, 17 August 2007 (UTC)
By induction I believe this is true, even if no sources to support it:
Omnitruncated n-simplices | |||||||
---|---|---|---|---|---|---|---|
n |
Uniform polytope ( Omnitruncated (n-1)- simplex) Schläfli symbol group: Coxeter-Dynkin diagram |
Coxeter plane projection | Picture | Tessellation A~n-1 or Pn Coxeter group |
Vertices n! |
Facets 2n-2 |
Facet counts by type |
2 | Interval t0{} A1: |
Apeirogon |
2 | 2 | |||
3 |
Hexagon (Truncated triangle) t0,1{3} A2: |
Hexagonal tiling |
6 | 6 | 2*3 {} | ||
4 |
Truncated octahedron (Omnitruncated tetrahedron) t0,1,2{3,3} A3: |
Bitruncated cubic honeycomb |
24 | 14 | 2*4 t0,1{3} + 6 {}x{} | ||
5 |
Omnitruncated 5-cell t0,1,2,3{3,3,3} A4: |
120 | 30 | 2*5 t0,1,2{3,3} + 2*10 t0,1{3}x{} | |||
6 |
Omnitruncated 5-simplex t0,1,2,3,4{3,3,3,3} A5: |
720 | 62 | 2*6 t0,1,2,3{3,3,3} + 2*15 t0,1,2{3,3} + 20 t0,1{3}xt0,1{3} | |||
7 |
Omnitruncated 6-simplex t0,1,2,3,4,5{3,3,3,3,3} A6: |
5040 | 126 | 2*7 t0,1,2,3,4{3,3,3,3} + 2*21 t0,1,2,3{3,3,3} + 35 t0,1,2{3,3}xt0,1{3} | |||
8 |
Omnitruncated 7-simplex t0,1,2,3,4,5,6{3,3,3,3,3,3} A7: |
40320 | 254 | ||||
9 |
Omnitruncated 8-simplex t0,1,2,3,4,5,6,7{3,3,3,3,3,3,3} A8: |
362880 | 510 | ||||
... | |||||||
n | Omnitruncated (n-1)-simplex t0,1,..,n-2{3n-2} An-1:... |
n! | 2n-2 | Σ[i=0..n-3] C(n,i)t0,...,i-1{3i-1}xt0,...,n-2-i{3n-2-i} |
Tom Ruen ( talk) 00:13, 25 November 2007 (UTC). (Expanded into a table) Tom Ruen ( talk) 07:24, 10 December 2007 (UTC)
Hi Tom Ruen,
I've found an elegant proof of your conjecture that the order-n permutohedron is an omnitruncated simplex. I'm not sure if this would be Original Research, so I'm refraining from posting this on Wikipedia for now, but I thought you might be interested in it. The key observation is that the omnitruncated n-simplex occurs as facets in an omnitruncated (n+1)-cube. In particular, it occurs in the "diagonal" position, in the positions parallel to the hyperplanes of the (n+1)-cross's facets (i.e., correponding to the vertices of an n-cube). The Cartesian coordinates of an omnitruncated n-cube can be obtained as follows: - We generate an n-dimensional base point based on the following steps, and
- In 1D, the point is simply <1>. - In n dimensions, we obtain the base point by appending the sum of the largest
The diagonal facet of an omnitruncated n-cube is simply the convex hull of all permutations of the base point, but without permutation of sign (i.e., take all non-negative coordinates only). Now, since the shape of the convex hull of these points is invariant under translation and scaling, we may subtract <1,1,1,...,1> and reduce the coordinates to permutations of <0, √2, 2√2, 3√2, ..., n√2>. Then, dividing by √2, we get permutations of <0, 1, 2, 3, ..., n>. This is the permutohedron of order n. QED. --T |
This week I was generating coordinates for the truncations of the regular n-simplices, and found Tetracube's page User:Tetracube/Uniform_polytera for n-orthoplexes, and realized the n-simplices could be generated in (n+1)-space as facets, and this inductive enumeration shows the Omnitruncated n-simplex is a representation of the 'n-permutohedron, and the lower truncation forms come out equally with permutations filtered by repeating coordinates of smaller integers of unringed nodes. Anyway, pretty cool, proved in my mind, sources or not: User:Tetracube/Uniform_polytera#Simplex coordinates Tom Ruen ( talk) 03:48, 28 July 2010 (UTC)
In math literatute I've usually seen the term spelled "permutAhedron". Why is it "permutOhedron" here? Maybe my sample is biased, but is there any particular reason either way? I'd think, at the least, the opening sentence should have both spellings. Zaslav ( talk) 04:46, 25 June 2011 (UTC)
I have great respect for David Eppstein, but he seems to be backing a losing horse in this matter. I just did a Google search, and this Wikipedia page was the only hit that preferred the spelling with an "o"; one other page gave both, but preferred "a"; the other 28 used only "a". LyleRamshaw ( talk) 01:05, 25 February 2017 (UTC)
5 years later, and they still seem to be neck and neck. MathSciNet has 101 "permutahedron" hits and 97 "permutohedron" hits. Personally I agree with David, but it's probably just a bias in the literature I'm familiar with. I think it's handled well in any case. 172.250.24.180 ( talk) 04:50, 17 August 2022 (UTC)
Number of set compositions (ordered set partitions) of n items into k parts. Number of k dimensional 'faces' of the n dimensional permutohedron (see Simion, p. 162). - Mitch Harris, Jan 16 2007
I think that this description of the triangle in the OEIS contains two mistakes: It actually is the number of n-k-dimensional faces, and it is the permutohedron of order n (or the n-1-dimensional permutohedron). It's difficult to correct stuff there. Maybe this mistake should be mentioned in references to this sequence. Watchduck ( quack) 23:38, 9 August 2013 (UTC)
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 |
I just corrected it in the OEIS: Number of (n-k)-dimensional 'faces' of the permutohedron of order n (i.e. the (n-1)-dimensional permutohedron).
In case there is any discussion, here is an example for n=4:
The permutohedron of order 4 (i.e. the 3-dimensional permutohedron) is the
truncated octahedron.
It has 1 cell (3-dimensional face), 14 faces (2-dimensional faces), 36 edges (1-dimensional faces), 24 vertices (0-dimensional faces)
Watchduck (
quack) 19:07, 29 October 2014 (UTC)
For a project at University, I've edited the main file of this article changing the edges' color so that they are not mistaken any more. I'm not sure whether changing it or leaving the old one. Maybe you @ Watchduck: can tell me what to do... Jordiventura96 ( talk) 00:24, 6 January 2020 (UTC)
I think since 52.144.34.243 started to confuse permutohedron and Cayley graph in February 2019, the intro has become more confusing than helpful. I think the version before was just fine.
The addition that the permutations can be 0-based also makes sense to me. (One could just write "permutations of the first n natural numbers".)
Right now the old intro is followed by a sentence to the effect, that the elements of the permuted vector can be any rational numbers. Such a generalized permutohedron could be described in the article, if relevant. But I don't think it belongs in the intro.
The statement after that seems to originate from one added by the IP, which was:
Zaslav has then gradually changed that to:
This is clearly a confusion of the permutohedron with the related Cayley graph. At least to me an "adjacent transposition" is clearly one that swaps adjacent places.
But in the permutohedron the edges correspond to all possible transpositions. Just the swapped values are adjacent (i.e. the swapped things on these places).
Here I have written what I hope to be a clarification. (Let me know if you think it's not.)
The intro should be only about the permutohedron. I will change the article accordingly. Watchduck ( quack) 20:32, 24 January 2020 (UTC)
One sentence reads:
"More generally, V. Joseph Bowman (1972) uses that term for any polytope whose vertices have a bijection with the permutations of some set."
So, any polytope with exactly n! vertices would then be called a permutohedron???
Either 1) there is more to what Bowman (1972) proposes, or else 2) this fact is so incompatible with intelligent geometry that it does not belong in the article. 216.161.117.162 ( talk) 19:10, 26 September 2020 (UTC)
This article is almost incomprehensible. Here is an example of why.
The first two paragraphs of the section Vertices, edges, and facets read as follows:
"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.
"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."
Consider the phrase: "consisting of the vertices in which all coordinates in positions in S are smaller than all coordinates in positions not in S".
All coordinates WHERE??? No Euclidean space has been mentioned. So a reader will not have any idea of WHERE these coordinates are supposed to exist.
This is unfortunately typical of this article. 65.141.95.170 ( talk) 19:53, 3 November 2020 (UTC)
Text and explanations | |
---|---|
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 . | (Based on what rule?) |
Each edge has length √2, and connects two vertices | |
that differ by swapping two coordinates the values of which differ by one. | Green edge 123–132 in
swaps 2 and 3. So does 1234–1324 in . |
The permutohedron has one facet for each nonempty proper subset S of {1, 2, 3, ..., n}, | Those are all
subsets except the empty set and the set itself. The following files show permutohedron-like Cayley graphs. Reading the square matrices by row gives the coordinates. Reading them by column gives the corresponding permutohedron coordinates. In the facets are the 1-faces a.k.a. edges. In they are the (2-)faces (hexagons and squares). The facets are represented by two-line matrices. Their first line is the subset. E.g. in the hexagon the top edge corresponds to the subset {2} and the bottom edge to {1, 3}. |
consisting of the vertices | E.g. the vertices of the hexagons and squares. |
in which all coordinates in positions in S are smaller than all coordinates in positions not in S. |
This is indeed difficult. First note that a coordinate is one value, not the tuple. S is the subset corresponding to the facet. Its elements are now called positions. Read the square matrices in this file by column to get the coordinates of the permutohedron. Consider the top left hexagon where S is {2}. So the positions is S are {2} and those not in S are {1, 3, 4}. Look at the six vertices. Their coordinate in position 2 is always 1, which is of course smaller than the other three. Consider the square one the left where S is {2, 3}. So the positions in S are {2, 3} and those not is S are {1, 4}. Look at the four vertices. Their coordinates on positions 2 and 3 are 1 and 2, which is smaller than those on positions 1 and 4, which are 3 and 4. |
Thus, the total number of facets is 2n − 2. | The number of subsets is a power of two, and we excluded two. |
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: |
has oB(3) = 13 and has oB(4) = 75 little matrices. |
a face of dimension d corresponds to a strict weak ordering in which there are n − d equivalence classes. |
The equivalence classes (or blocks of the set partition) are the rows of these matrices. |
Because of this correspondence, the number of faces is given by the ordered Bell numbers. |
vertices, edges, facets, faces 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 number of -dimensional faces in a permutohedron of order is found in the triangle , where are the Stirling numbers of the second kind | |
(sequence
A019538 in the
OEIS) — shown on the right, together with its row sums, the ordered Bell numbers. |
Did you not understand that just from reading this section? ;) Greetings, Watchduck ( quack) 02:14, 5 November 2020 (UTC)
vertices, edges, facets, faces Face dimension d = n − k. |
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. The number of edges is (n − 1) n!/2, and their length is √2.
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 (3, 2, 1, 4) and (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 2n − 2, because they correspond to non-empty proper subsets S of {1 … n}. The vertices of a facet corresponding to subset S have in common, that their coordinates on places in S are smaller than the rest.
More generally, the faces of dimensions 0 (vertices) to n − 1 (the permutohedron itself) correspond to the strict weak orderings of the set {1 … n}. So the number of all faces is the n-th ordered Bell number. A face of dimension d corresponds to an ordering with k = n − d equivalence classes.
Face examples | |
---|---|
order 3 | order 4 |
The images above show the
face lattices of the permutohedra of order 3 and 4 (without the empty faces). The vertex labels a | b | c | d interpreted as permutations (a, b, c, d) are those forming the Cayley graph. The before mentioned facets are among these faces, and correspond to orderings with two equivalence classes. The images below show how the facets of the n-permutohedron correspond to the
simplical projection of the n-
cube. | |
The number of faces of dimension d = n − k in the permutohedron of order n is given by the triangle T (sequence
A019538 in the
OEIS):
with representing the
Stirling numbers of the second kind
It is shown on the right together with its row sums, the
ordered Bell numbers.
Added source: Lancia, Giuseppe (2018), Compact extended linear programming models, Cham, Switzerland: Springer, ISBN 978-3-319-63975-8
truncated octahedron |
truncated cuboctahedron |
truncated icosidodecahedron |
source |
---|---|---|---|
descriptions in the source | |||
signed p. | This term is sometimes used for the convex hull of the
signed permutations. e.g. On Flag Vectors..., Mixed volumes of hypersimplices | ||
p. of type A3 | p. of type B3 | https://books.google.de/books?id=W_SPdwfPTw8C&pg=PA83#v=onepage&q&f=false | |
p. for the symmetric group S4 | p. for the hyperoctahedral group W3 | p. for W(H3) | https://books.google.de/books?id=Y01d6g5UemQC&pg=PA135#v=onepage&q&f=false |
TBC, started by Watchduck ( quack) 16:57, 15 November 2020 (UTC)
The part about "The permutohedron-like Cayley graph of S4" and a large part of the page https://commons.wikimedia.org/wiki/Category:Permutohedron_of_order_4_(raytraced)#Permutohedron_vs._Cayley_graph is superfluous. One only needs to realize that applying a permutation on one side swaps places, and applying it on the other side swaps values. Both compared graphs are Cayley graphs, one is left-Cayley, the other is right-Cayley. Leen Droogendijk ( talk) 11:08, 9 June 2021 (UTC)
A fact from Permutohedron appeared on Wikipedia's
Main Page in the
Did you know column on 17 August 2007. The text of the entry was as follows:
|
This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
The article claims that every permutohedron is a zonotope. This is morally true, but unfortunately a zonotope is defined to be a 3-dimensional thing, while a permutohedron can be n-dimensional for any n. This can't be fixed in the permutohedron article, it needs to be fixed in the zonotope article. Adam1729 01:16, 17 August 2007 (UTC)
By induction I believe this is true, even if no sources to support it:
Omnitruncated n-simplices | |||||||
---|---|---|---|---|---|---|---|
n |
Uniform polytope ( Omnitruncated (n-1)- simplex) Schläfli symbol group: Coxeter-Dynkin diagram |
Coxeter plane projection | Picture | Tessellation A~n-1 or Pn Coxeter group |
Vertices n! |
Facets 2n-2 |
Facet counts by type |
2 | Interval t0{} A1: |
Apeirogon |
2 | 2 | |||
3 |
Hexagon (Truncated triangle) t0,1{3} A2: |
Hexagonal tiling |
6 | 6 | 2*3 {} | ||
4 |
Truncated octahedron (Omnitruncated tetrahedron) t0,1,2{3,3} A3: |
Bitruncated cubic honeycomb |
24 | 14 | 2*4 t0,1{3} + 6 {}x{} | ||
5 |
Omnitruncated 5-cell t0,1,2,3{3,3,3} A4: |
120 | 30 | 2*5 t0,1,2{3,3} + 2*10 t0,1{3}x{} | |||
6 |
Omnitruncated 5-simplex t0,1,2,3,4{3,3,3,3} A5: |
720 | 62 | 2*6 t0,1,2,3{3,3,3} + 2*15 t0,1,2{3,3} + 20 t0,1{3}xt0,1{3} | |||
7 |
Omnitruncated 6-simplex t0,1,2,3,4,5{3,3,3,3,3} A6: |
5040 | 126 | 2*7 t0,1,2,3,4{3,3,3,3} + 2*21 t0,1,2,3{3,3,3} + 35 t0,1,2{3,3}xt0,1{3} | |||
8 |
Omnitruncated 7-simplex t0,1,2,3,4,5,6{3,3,3,3,3,3} A7: |
40320 | 254 | ||||
9 |
Omnitruncated 8-simplex t0,1,2,3,4,5,6,7{3,3,3,3,3,3,3} A8: |
362880 | 510 | ||||
... | |||||||
n | Omnitruncated (n-1)-simplex t0,1,..,n-2{3n-2} An-1:... |
n! | 2n-2 | Σ[i=0..n-3] C(n,i)t0,...,i-1{3i-1}xt0,...,n-2-i{3n-2-i} |
Tom Ruen ( talk) 00:13, 25 November 2007 (UTC). (Expanded into a table) Tom Ruen ( talk) 07:24, 10 December 2007 (UTC)
Hi Tom Ruen,
I've found an elegant proof of your conjecture that the order-n permutohedron is an omnitruncated simplex. I'm not sure if this would be Original Research, so I'm refraining from posting this on Wikipedia for now, but I thought you might be interested in it. The key observation is that the omnitruncated n-simplex occurs as facets in an omnitruncated (n+1)-cube. In particular, it occurs in the "diagonal" position, in the positions parallel to the hyperplanes of the (n+1)-cross's facets (i.e., correponding to the vertices of an n-cube). The Cartesian coordinates of an omnitruncated n-cube can be obtained as follows: - We generate an n-dimensional base point based on the following steps, and
- In 1D, the point is simply <1>. - In n dimensions, we obtain the base point by appending the sum of the largest
The diagonal facet of an omnitruncated n-cube is simply the convex hull of all permutations of the base point, but without permutation of sign (i.e., take all non-negative coordinates only). Now, since the shape of the convex hull of these points is invariant under translation and scaling, we may subtract <1,1,1,...,1> and reduce the coordinates to permutations of <0, √2, 2√2, 3√2, ..., n√2>. Then, dividing by √2, we get permutations of <0, 1, 2, 3, ..., n>. This is the permutohedron of order n. QED. --T |
This week I was generating coordinates for the truncations of the regular n-simplices, and found Tetracube's page User:Tetracube/Uniform_polytera for n-orthoplexes, and realized the n-simplices could be generated in (n+1)-space as facets, and this inductive enumeration shows the Omnitruncated n-simplex is a representation of the 'n-permutohedron, and the lower truncation forms come out equally with permutations filtered by repeating coordinates of smaller integers of unringed nodes. Anyway, pretty cool, proved in my mind, sources or not: User:Tetracube/Uniform_polytera#Simplex coordinates Tom Ruen ( talk) 03:48, 28 July 2010 (UTC)
In math literatute I've usually seen the term spelled "permutAhedron". Why is it "permutOhedron" here? Maybe my sample is biased, but is there any particular reason either way? I'd think, at the least, the opening sentence should have both spellings. Zaslav ( talk) 04:46, 25 June 2011 (UTC)
I have great respect for David Eppstein, but he seems to be backing a losing horse in this matter. I just did a Google search, and this Wikipedia page was the only hit that preferred the spelling with an "o"; one other page gave both, but preferred "a"; the other 28 used only "a". LyleRamshaw ( talk) 01:05, 25 February 2017 (UTC)
5 years later, and they still seem to be neck and neck. MathSciNet has 101 "permutahedron" hits and 97 "permutohedron" hits. Personally I agree with David, but it's probably just a bias in the literature I'm familiar with. I think it's handled well in any case. 172.250.24.180 ( talk) 04:50, 17 August 2022 (UTC)
Number of set compositions (ordered set partitions) of n items into k parts. Number of k dimensional 'faces' of the n dimensional permutohedron (see Simion, p. 162). - Mitch Harris, Jan 16 2007
I think that this description of the triangle in the OEIS contains two mistakes: It actually is the number of n-k-dimensional faces, and it is the permutohedron of order n (or the n-1-dimensional permutohedron). It's difficult to correct stuff there. Maybe this mistake should be mentioned in references to this sequence. Watchduck ( quack) 23:38, 9 August 2013 (UTC)
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 |
I just corrected it in the OEIS: Number of (n-k)-dimensional 'faces' of the permutohedron of order n (i.e. the (n-1)-dimensional permutohedron).
In case there is any discussion, here is an example for n=4:
The permutohedron of order 4 (i.e. the 3-dimensional permutohedron) is the
truncated octahedron.
It has 1 cell (3-dimensional face), 14 faces (2-dimensional faces), 36 edges (1-dimensional faces), 24 vertices (0-dimensional faces)
Watchduck (
quack) 19:07, 29 October 2014 (UTC)
For a project at University, I've edited the main file of this article changing the edges' color so that they are not mistaken any more. I'm not sure whether changing it or leaving the old one. Maybe you @ Watchduck: can tell me what to do... Jordiventura96 ( talk) 00:24, 6 January 2020 (UTC)
I think since 52.144.34.243 started to confuse permutohedron and Cayley graph in February 2019, the intro has become more confusing than helpful. I think the version before was just fine.
The addition that the permutations can be 0-based also makes sense to me. (One could just write "permutations of the first n natural numbers".)
Right now the old intro is followed by a sentence to the effect, that the elements of the permuted vector can be any rational numbers. Such a generalized permutohedron could be described in the article, if relevant. But I don't think it belongs in the intro.
The statement after that seems to originate from one added by the IP, which was:
Zaslav has then gradually changed that to:
This is clearly a confusion of the permutohedron with the related Cayley graph. At least to me an "adjacent transposition" is clearly one that swaps adjacent places.
But in the permutohedron the edges correspond to all possible transpositions. Just the swapped values are adjacent (i.e. the swapped things on these places).
Here I have written what I hope to be a clarification. (Let me know if you think it's not.)
The intro should be only about the permutohedron. I will change the article accordingly. Watchduck ( quack) 20:32, 24 January 2020 (UTC)
One sentence reads:
"More generally, V. Joseph Bowman (1972) uses that term for any polytope whose vertices have a bijection with the permutations of some set."
So, any polytope with exactly n! vertices would then be called a permutohedron???
Either 1) there is more to what Bowman (1972) proposes, or else 2) this fact is so incompatible with intelligent geometry that it does not belong in the article. 216.161.117.162 ( talk) 19:10, 26 September 2020 (UTC)
This article is almost incomprehensible. Here is an example of why.
The first two paragraphs of the section Vertices, edges, and facets read as follows:
"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.
"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."
Consider the phrase: "consisting of the vertices in which all coordinates in positions in S are smaller than all coordinates in positions not in S".
All coordinates WHERE??? No Euclidean space has been mentioned. So a reader will not have any idea of WHERE these coordinates are supposed to exist.
This is unfortunately typical of this article. 65.141.95.170 ( talk) 19:53, 3 November 2020 (UTC)
Text and explanations | |
---|---|
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 . | (Based on what rule?) |
Each edge has length √2, and connects two vertices | |
that differ by swapping two coordinates the values of which differ by one. | Green edge 123–132 in
swaps 2 and 3. So does 1234–1324 in . |
The permutohedron has one facet for each nonempty proper subset S of {1, 2, 3, ..., n}, | Those are all
subsets except the empty set and the set itself. The following files show permutohedron-like Cayley graphs. Reading the square matrices by row gives the coordinates. Reading them by column gives the corresponding permutohedron coordinates. In the facets are the 1-faces a.k.a. edges. In they are the (2-)faces (hexagons and squares). The facets are represented by two-line matrices. Their first line is the subset. E.g. in the hexagon the top edge corresponds to the subset {2} and the bottom edge to {1, 3}. |
consisting of the vertices | E.g. the vertices of the hexagons and squares. |
in which all coordinates in positions in S are smaller than all coordinates in positions not in S. |
This is indeed difficult. First note that a coordinate is one value, not the tuple. S is the subset corresponding to the facet. Its elements are now called positions. Read the square matrices in this file by column to get the coordinates of the permutohedron. Consider the top left hexagon where S is {2}. So the positions is S are {2} and those not in S are {1, 3, 4}. Look at the six vertices. Their coordinate in position 2 is always 1, which is of course smaller than the other three. Consider the square one the left where S is {2, 3}. So the positions in S are {2, 3} and those not is S are {1, 4}. Look at the four vertices. Their coordinates on positions 2 and 3 are 1 and 2, which is smaller than those on positions 1 and 4, which are 3 and 4. |
Thus, the total number of facets is 2n − 2. | The number of subsets is a power of two, and we excluded two. |
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: |
has oB(3) = 13 and has oB(4) = 75 little matrices. |
a face of dimension d corresponds to a strict weak ordering in which there are n − d equivalence classes. |
The equivalence classes (or blocks of the set partition) are the rows of these matrices. |
Because of this correspondence, the number of faces is given by the ordered Bell numbers. |
vertices, edges, facets, faces 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 number of -dimensional faces in a permutohedron of order is found in the triangle , where are the Stirling numbers of the second kind | |
(sequence
A019538 in the
OEIS) — shown on the right, together with its row sums, the ordered Bell numbers. |
Did you not understand that just from reading this section? ;) Greetings, Watchduck ( quack) 02:14, 5 November 2020 (UTC)
vertices, edges, facets, faces Face dimension d = n − k. |
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. The number of edges is (n − 1) n!/2, and their length is √2.
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 (3, 2, 1, 4) and (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 2n − 2, because they correspond to non-empty proper subsets S of {1 … n}. The vertices of a facet corresponding to subset S have in common, that their coordinates on places in S are smaller than the rest.
More generally, the faces of dimensions 0 (vertices) to n − 1 (the permutohedron itself) correspond to the strict weak orderings of the set {1 … n}. So the number of all faces is the n-th ordered Bell number. A face of dimension d corresponds to an ordering with k = n − d equivalence classes.
Face examples | |
---|---|
order 3 | order 4 |
The images above show the
face lattices of the permutohedra of order 3 and 4 (without the empty faces). The vertex labels a | b | c | d interpreted as permutations (a, b, c, d) are those forming the Cayley graph. The before mentioned facets are among these faces, and correspond to orderings with two equivalence classes. The images below show how the facets of the n-permutohedron correspond to the
simplical projection of the n-
cube. | |
The number of faces of dimension d = n − k in the permutohedron of order n is given by the triangle T (sequence
A019538 in the
OEIS):
with representing the
Stirling numbers of the second kind
It is shown on the right together with its row sums, the
ordered Bell numbers.
Added source: Lancia, Giuseppe (2018), Compact extended linear programming models, Cham, Switzerland: Springer, ISBN 978-3-319-63975-8
truncated octahedron |
truncated cuboctahedron |
truncated icosidodecahedron |
source |
---|---|---|---|
descriptions in the source | |||
signed p. | This term is sometimes used for the convex hull of the
signed permutations. e.g. On Flag Vectors..., Mixed volumes of hypersimplices | ||
p. of type A3 | p. of type B3 | https://books.google.de/books?id=W_SPdwfPTw8C&pg=PA83#v=onepage&q&f=false | |
p. for the symmetric group S4 | p. for the hyperoctahedral group W3 | p. for W(H3) | https://books.google.de/books?id=Y01d6g5UemQC&pg=PA135#v=onepage&q&f=false |
TBC, started by Watchduck ( quack) 16:57, 15 November 2020 (UTC)
The part about "The permutohedron-like Cayley graph of S4" and a large part of the page https://commons.wikimedia.org/wiki/Category:Permutohedron_of_order_4_(raytraced)#Permutohedron_vs._Cayley_graph is superfluous. One only needs to realize that applying a permutation on one side swaps places, and applying it on the other side swaps values. Both compared graphs are Cayley graphs, one is left-Cayley, the other is right-Cayley. Leen Droogendijk ( talk) 11:08, 9 June 2021 (UTC)