5

This MO-Q details the sense in which an associahedron is a product of lower dimensional associahedra, and this MSE-Q indicates the same is true for permutohedra.

Is there a reference which classifies the families of convex polytopes for which this relationship holds and provides more detail?

(Edit 6/6/2016 in response to Alen Knutson's comments)

For the n-Dim simplices, the n-D simplex can be generated by connecting the vertices of the (n-1)-D simplex to a point in a dimension orthogonal to those of the (n-1)-D simplex, so each set of k-D faces is associated to one unique simplex and the face polynomial $\frac{(x+1)^{n+1} - 1}{x}$ has no refined components.

For the hypercubes, the n-Dim hypercube can be generated by translating the (n-1)-Dim hypercube in an orthogonal direction, so again each set of k-D faces is associated to a unique lower order hypercube and the face polynomial is $(x+2)^n$ with no refined components.

The simplices and the hypercubes have a higher degree of symmetry and much simpler geometric constructions than the permutahedra and associahedra, giving an extremely rough classification scheme for the two sets of convex polytopes--one in which the faces are polytopes of the same family, the other, products of polytopes of the same family.

Edit (Dec 2017):

For the permutohedra and associahedra, see pg. 5 of "Hopf monoids and generalized permutahedra" by Aguiar and Ardila in which we find " ... every face of a permutahedron is a product of permutahedra. ... every face of an associahedron is a product of associahedra ... ."

Edit (June 2018):

The permutahedra and associahedra share some common properties. The permutohedra and their simplicial duals share the same symmetric h-vectors as well as the associahedra and their simplicial duals. (I don't know how common or relevant this property is.) Furthermore, Postnikov in Positive Grassmannian and Polyhedral Subdivisions states on pg. 17 the following:

(1) For a projection of the (n-1)-simplex to an n-gon, π-induced subdivisions are exactly the subdivisions of the n-gon by noncrossing chords. All of them are coherent. The fiber polytope (or the secondary polytope) in this case is the Stasheff associahedron.

(2) For a projection of the n-hypercube to a 1-dimensional line segment, the fiber polytope is the permutohedron.

For more notes on fiber polytopes, see Combinatorics of Polytopes by Barvinok.

(Edit Nov. 5, 2018)

From "Higher homotopy operations" by Blanc and Markl:

Definition. A family of polytopes is a sequence $F = (P_n)^\infty_{n=0}$ of polytopes, starting with $P_0 = {pt}$, such that $dim(P_n) = n$, and each facet of $P_n$ is isomorphic to some product of lower dimensional polytopes from $F$. ... Many familiar examples of polytopes fit into such families:

The authors then list the n-simplices, hypercubes, associahedra, and permutohedra.

Edit (Sept. 2019): In "[The diagonal of the associahedra] 7" Masuda, Thomas, Tonks, and Vallette discuss face-coherent families of convex polytopes such as the simplices, hypercubes, and associahedra.

Edit (Oct. 30. 2020):

From the references in the comments below, each face of a zonotope, orbit, cyclic, matroid, or alcoved polytope is either a polytope of the same family or a product of polytopes of the same family.

Tom Copeland
  • 9,937
  • 1
    Is this saying more than "each face is a product of polytopes from the family"? If it's only that, then I don't see that any sort of classification is possible. – Allen Knutson Jun 04 '16 at 12:23
  • @AllenKnutson, no more, no less, as encoded in the subscripts and exponents of the monomials of the refined face partition polynomials. – Tom Copeland Jun 04 '16 at 12:53
  • Then take any set of polytopes. Close the set under taking faces. Now it has your property. E.g., take all the permutahedra of dimension $\leq 17$. I think you'll need some positive direction like, if a polytope's facets all are products from the set, plus some extra condition, then that polytope should be in the set. I don't know what this condition would be with the set of associahedra or permutahedra. – Allen Knutson Jun 04 '16 at 22:24
  • @AllenKnutson, a related question for me is "Why do refined face partition-polynomials exist that pose a bijection between the faces of these two families of polytopes and the partitions of the integers?" For the permutohedra, I suppose the answer should relate the structure of the polytopes to the Faa di Bruno formula for composing an e.g.f. with 1/x. For the n-simplices, this bijection doesn't hold whereas the geometric constuction of higher dim simplices from lower is simple. – Tom Copeland Jun 04 '16 at 23:23
  • Should shed some light on relations among polytopes and Hopf algebras through the antipode for Hopf algebras characterizing the composition of o.g.f.s. – Tom Copeland Jun 04 '16 at 23:34
  • @AllenKnutson, see my edit for a naive classification scheme. I'm hoping someone has had some more profound insights. (I'll delete this comment soon.) – Tom Copeland Jun 06 '16 at 19:26
  • Certainly permutahedra have high (e.g. vertex-transitive) symmetry, and indeed, simplices and cubes are (faces of) permutahedra. I still think you need a property that says "Any polytope whose faces are in the set, plus something, should also be in the set." – Allen Knutson Jun 06 '16 at 19:47
  • @AllenKnutson, I don't understand your last comment on n-simplices (triangles, tetrahedron, ...) or hypercubes (squares or tetragons, cubes, ...) being the faces of the 3-D permutahedron. How is a hexagon a triangle or square, for example? – Tom Copeland Jun 06 '16 at 20:36
  • (a) I didn't say 3-d, though, a rectangle is indeed a face of a 3-d permutahedron. (b) For me, a permutahedron is the convex hull of $S_n\cdot \vec v$, where $\vec v$ may have repeated entries. A degenerate hexagon can be a triangle (the $\vec v = (1,0,0)$ case). – Allen Knutson Jun 07 '16 at 00:31
  • @AllenKnutson : Well, then in your case I agree with you--you'd better stipulate a lot of:additional properties to address some sort of classification scheme. I mean that the n-d associahedron of the family of polytopes called the associahedra is a Cartesian product of the lower dim associahedra as Loday described, and the same holds true for the family called permutahedra. This doesn't hold for the family of hypercubes nor the family of n-simplices, as reflected in the information in the illustrated face polynomials. – Tom Copeland Jun 07 '16 at 01:25
  • All right, for your face polynomial stuff I guess it's reasonable to disallow degenerate cases. I still don't know what "is a Cartesian product as Loday described" means. – Allen Knutson Jun 07 '16 at 01:51
  • Let us continue this discussion in chat. – Tom Copeland Jun 07 '16 at 17:30
  • Also Fomin and Reading on pg. 31 of "Root systems and generalized associahedra " state, "For example, each face (of an associahedron) is the direct product of smaller associahedra." https://arxiv.org/abs/math/0505518 – Tom Copeland Jun 28 '17 at 00:46
  • Also see Schobel and Veselov, "Separation coordinates, moduli spaces, and Stasheff polytopes" https://arxiv.org/abs/1307.6132 – Tom Copeland Nov 21 '17 at 12:22
  • 1
    For an interesting class of polytopes closed under taking faces, see http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r65/pdf. As a special case, faces of cyclic polytopes are cyclic polytopes. – Richard Stanley Jun 26 '18 at 14:47
  • Stanley links to "Flag vectors of multiplicial polytopes" by Margaret M. Bayer. – Tom Copeland Sep 07 '19 at 17:15
  • See also "The Hopf Monoid of Orbit Polytopes" by Supina (https://arxiv.org/abs/1904.08437): Each face of an orbit polytope decomposes as a product of lower-dimensional orbit polytopes. In particular, each facet of an orbit polytope decomposes as a product of two orbit polytopes. This will allow us to define a coproduct of orbit polytopes ... . – Tom Copeland Feb 10 '20 at 16:22
  • Related to factorization of associahedra: "Causal Diamonds, Cluster Polytopes and Scattering Amplitudes" by Nima Arkani-Hamed, Song He, Giulio Salvatori, and Hugh Thomas https://arxiv.org/abs/1912.12948 – Tom Copeland Apr 07 '20 at 23:27
  • From "Positive configuration space" by Nima Arkani-Hamed, Thomas Lam, Marcus Spradlin: Every face of a matroid polytope (resp. alcoved polytope) is a matroid polytope (resp. alcoved polytope). – Tom Copeland Oct 10 '20 at 19:02
  • From "Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra" by Beck and Robins: . . . we study a concrete class of polytopes—projections of cubes, which go by the name zonotopes—whose discrete volume is tractable and has neat connections to number theory and graph theory. . . . each face of a zonotope is again a zonotope . . . The permutahedron is a simple zonotope and as such quite a rare animal. – Tom Copeland Nov 01 '20 at 02:33
  • The quotes from the Beck and Robins ref above comes from 19 June 2020 version of their paper not the 2009 version, which mentions neither zonotopes nor permutahedra. – Tom Copeland Nov 01 '20 at 22:28
  • On p. 9 of "Covariant color-kinematics duality, Hopf algebras and permutohedra?", Cao, Dong, He, and Zhang discuss the factorization of the faces of the 3-D permutahedron. – Tom Copeland Dec 04 '22 at 18:39
  • On types of generalized permutahedra (in 3-D at least), see "Cells in Coxeter groups" by Gunnells {https://www.ams.org/notices/200605/fea-gunnells.pdf}. – Tom Copeland Apr 16 '23 at 17:56
  • See "A compact data structure for high dimensional Coxeter-Freudenthal-Kuhn triangulations: by Boissonnat et al. – Tom Copeland Mar 27 '24 at 15:03

0 Answers0