Talk:Permutohedron

Zonotopes

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)

Actually, I think that's a misreading of the zonotope article (a redirect to zonohedron): it defines a zonohedron as a three-dimensional thing, and a zonotope as arbitrary dimensional. But the zonotope definition was buried in the middle of the article; I just made it more prominent. —David Eppstein 04:08, 18 August 2007 (UTC)

Thanks. The confusion is partly because a ...hedron is 3d whereas a ...tope is n-d, except for a permutohedron. Maybe we should say this. Adam1729 01:12, 19 August 2007 (UTC)

Another, closely related exception: associahedron. Arcfrk 05:19, 22 August 2007 (UTC)

Omnitruncated n-simplices

By induction I believe this is true, even if no sources to support it:

The permutohedron of order n is an omnitruncated (n − 1)-simplex.:

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)

This is certainly very compelling. Perhaps one approach to prove this might be to explicate the relationship of the n-order permutohedron with the n-hypercube: Note, for example, that the line segment is the intersection of a square with a diagonal line at the appropriate depth from one of its vertices. The hexagon is the intersection of a cube with the plane wherein lies the permutohedron, which is at an appropriate depth from one of the cube's corners. I surmise that the truncated octahedron (omnitruncated tetrahedron) is the intersection of the corresponding hyperplane with the 4-cube at the appropriate depth. Now, the key to these observations is that truncating a corner of the n-cube yields an (n-1)-simplex, but if the truncating plane is moved deeper into the cube, eventually the simplex will intersect with other cube facets and thereby become truncated, rectified, and eventually omnitruncated(?). So if we can prove that the hyperplane that an n-permutohedron lies in is precisely the depth at which the (n-1)-simplex is omnitruncated, then we have established your conjecture.—Tetracube (talk) 00:24, 14 August 2008 (UTC)

Yes, it does look like an order-n permutohedron is constructed on the hyperplane cross-section (n+1)-hypercube. The hyperplane is contained by the hypercube center and appears to pass through the center of a set of ridges of each hypercube: vertices of square, mid-edges of cube, and mid-faces of tesseract, and mid-cells of penteract. But just a guess! Tom Ruen (talk) 04:24, 14 August 2008 (UTC)

I think this misses the point. We shouldn't be making and then trying to prove conjectures here, per WP:NOT. Not even on the talk page. We should be trying to determine whether someone else has already established this, and only if we can find appropriate reliably published sources should we add this to the article. —David Eppstein (talk) 00:55, 14 August 2008 (UTC)

Hmmmm, perhaps this wiki-talk page will inspire a paper to be published that will prove it? At least that was my secret inspiration to putting it here. :) My table seems defendable on this talk page, even if discussion on proving it doesn't, oops. For me, a computational construction would be a proof. We can compute and omnitruncated simplices from a Wythoff construction, and permutohedron vertices constructable via permutations of coordinates, and facets by a convex hull, and elements can be counted. If these are computed and vertices match to any level desired, that's a proof to me (or counter proof if wrong of course.) Anyway, from the papers I've seen, there's been nothing in this direction, all abstract stuff. :( Tom Ruen (talk) 04:24, 14 August 2008 (UTC)

I have found a proof for this conjecture. The key observation lies in the fact that an omnitruncated n-simplex occurs as corner facets in an omnitruncated (n+1)-cube. There is a trivial mapping from the Cartesian coordinates of the corner facet of an omnitruncated n-cube to a permutohedron of order n, thereby establishing the equivalence. However, since this is likely to be original research, I'm refraining from posting the proof here (I've emailed it to Tom Ruen for verification).—Tetracube (talk) 19:14, 25 November 2008 (UTC)

I got Tetracube's email, but don't have time now to try to follow it, but I see no problem having it posted here on the talk page. Tom Ruen (talk) 03:40, 26 November 2008 (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 then take all permutations of coordinates and sign (equivalent to reflecting across the mirrors corresponding with the Dynkin symbol for the n-cube). - In 1D, the point is simply <1>. - In n dimensions, we obtain the base point by appending the sum of the largest coordinate in the previous dimension with √2. For example, in 2D, our base point is <1, 1+√2>, which generates the octagon, and in 3D, our base point is <1, 1+√2, 1+2√2>, which generates the great rhombicubotahedron, and in 4D, <1, 1+√2, 1+2√2, 1+3√2> generates the omnitruncated tesseract. 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)

Spelling

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 think the "o" spelling is a little more common, and matches the original French spelling, so I it makes sense to keep it as the primary spelling. But I agree that there seems to be enough disagreement over this point to include the other spelling as a valid variant, so I've gone ahead and added it to the lede. —David Eppstein (talk) 05:09, 25 June 2011 (UTC)