4
$\begingroup$

I am a topologist and not quite familiar with the tools for building a polytope. I would like to build some topological polytope which is an somewhere in between permutohedron and associahedron which I will explain below.

Recall that the faces of $n$-th associahedron $K^n$ also known as Stasheff's polytope is indexed by $T_n$, rooted planar trees with with $n$ leaves.

It is also well known that the faces of $(n-1)$-th permutohedron, $P^{n-1}$, is indexed by $LT_n$, the set of rooted planar trees with levels with $n$ leaves (see Loday's paper for details). Loday, in the very same paper defined a map $$q: P^{n-1} \to K^n$$ which is induced by forgetful map from level trees to trees one that forgets level.

I want to build a polytope $Q^{n-1}$ whose cells are indexed by $YT_n$, the set of planar rooted trees with $n$-leaves where we specify the youngest child/children. There is a forgetful map $$LT_n \to YT_n$$ which is basically forgetting all the level except the top most level. Also there is a map $$YT_n \to T_n $$ which is basically forgetting the set of youngest children.

Thus the quotient map from $P^{n-1} \to K^{n}$ should factor through $Q^{n-1}$.

My question is how do I formally build the topological polytope $Q^{n-1}$ formally? How do I prove that that the boundary of $Q^{n-1}$ is homeomorphic to sphere or at least homotopic to sphere?

All of these above question becomes easier (may be) if we can realize this polytope as convexhull on set of vertices. Is there a possible convex model for such a polytope? I wonder if there exist one.

$\endgroup$

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ "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." Can you please elaborate? I am not quite sure how to do this part. $\endgroup$
    – Prasit
    Aug 20, 2014 at 1:06
  • $\begingroup$ Pages 9-11 of Forcey and Springfield explain how the map from the graph associahedron of the complete graph to the graph associahedron of the path graph is equivalent to forgetting the levels of a tree. I'll try to provide some more details of how the cyclohedron fits in. $\endgroup$ Aug 20, 2014 at 13:12
  • $\begingroup$ When we construct the trees associated to a tubing of a graph, where do the levelings of the tree come from? In particular, why do we get complete levelings when we begin with a complete graph, a "youngest leveling" when we have a cyclic graph, and no leveling when we have a path graph. $\endgroup$
    – Prasit
    Aug 20, 2014 at 15:22
  • $\begingroup$ I am confused about what is happening. Please "unaccept" this answer (for now). If I can figure out what is going on I will add something. $\endgroup$ Aug 20, 2014 at 18:39
1
$\begingroup$

There is a canonical thing to do if you have a lattice quotient of weak order on the symmetric group. Namely, you take the Coxeter fan (which has one maximal cone for each element of $S_n$) and you glue together the chambers that correspond to the same element in your quotient. This gives you a fan. The natural thing to hope for is that this fan will be the outer normal fan of a polytope. Checking whether or not that is true, is somewhat delicate. A thing which sometimes works is to consider taking the permutohedron and removing some of its defining inequalities (so that the resulting polytope gets bigger). It is possible to construct an associahedron in this way.

However, I checked, and the map you have described is not a lattice quotient of weak order. So I do not know of any canonical thing to do.

However, if I have correctly understood your definition of $YT$, the number of 0-cells in $YT_n$ is $2(n-2)\choose n-2$. This is the type $B/C$ Catalan number, and suggests that the thing you want to construct is the cyclohedron (also known as the Bott-Taubes polytope). Its vertices are naturally in bijection with $YT_n$. It isn't naturally constructed starting from the type $A$ permutohedron, but rather from the type $B/C$ permutohedron. I can add more details if this seems like it would be useful.

$\endgroup$
2
  • $\begingroup$ I do not know the exact number of elements for $YT_n$. But I can calculate the first few by hand. Note that if $n=2$ then there is exactly one tree with two leaves. If $n=3$ then there are $3$ of them (two binary tree and one corolla with 3 leaves). Child(ren) refers to the vertices. In the above case the tree itself determines the youngest child(ren). If $n=4$, $Q^{4-1}$ is precisely $P^3$. So number of cells is precisely number of cells in $P^3$ which is 13. the map from $P^n \to Q^n$ is homeomorphism for $n\leq 3$. But for $n>3$ the map from $P^n \to Q^n$ should be quotient maps. $\endgroup$
    – Prasit
    Aug 19, 2014 at 14:51
  • 1
    $\begingroup$ I have edited my answer to clarify that I believe $2(n-2)\choose (n-2)$ is the number of zero-cells in $YT_n$. (My indexing also disagreed with yours, and I fixed that too.) $\endgroup$ Aug 19, 2014 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.