Skip to main content
2 of 2
point out that my former answer is totally wrong
Hugh Thomas
  • 6.3k
  • 27
  • 50

Edited to add: I now think the answer below is completely wrong. The three-dimensional cyclohedron has 12 facets, while the three-dimensional polytope the OP is looking for should have 14. This is the number of facets of the permutohedron, and none of them collapse. (In fact, if I have correctly understood things, the facets of the polytope the OP wants should always be in natural bijection with the facets of the permutohedron of the same dimension.)


This is a different strategy from my previous answer, and I believe it is likely what you are looking for.

There is a construction due to Carr and Devadoss called "graph associahedron" which takes a graph, and gives you a polytope. See arXiv:math/0407229. The polytope is defined combinatorially in terms of "tubings" on the graph.

If your graph is a path, the result is the classical associahedron, and if your graph is a complete graph, the result is the permutohedron.

The cyclohedron is the graph associahedron for a cycle graph, and I expect that this is what you want. The simplest way to define its faces is to say that they are associated to cyclic parenthesizations of the word 1..$n$. The number of pairs of parentheses inserted gives you the codimension of the face. When I say cyclic, that means that you should read 1..$n$ cyclically. Thus, for $n=3$, there are 6 1-faces: the parentheses could be (1)23, 1(2)3, 12(3), (12)3, 1(23), or 1)2(3 (where this last one is allowed because of the cyclicity). There are also 6 0-faces: ((1)2)3, (1(2))3, 1(2(3)), 1((2)3), (1))2(3, and 1)2((3).

In order to interpret these as trees remembering the bottom vertex, you should do the usual thing to turn parenthesizations into trees, and then let the "bottom" vertex be the one including the number 1.

Removing an edge from the graph, gives you a map from the graph associahedron of the bigger graph to the graph associahedron of the smaller graph. This is Lemma 3.2 of arXiv:0908.3111 by Forcey and Springfield.

Once you note (as Forcey and Springfield do) that the cycle graph on $n$ vertices sits between the complete graph on $n$ vertices and the path on $n$ vertices, you get a sequence of maps of polytopes of the kind you want.

Hugh Thomas
  • 6.3k
  • 27
  • 50