# Why are we interested in permutahedra, associahedra, cyclohedra, …?

The following families of polytopes have received a lot of attention:

My question is simple: Why?

As I understand, at least the latter two were initially constructed by their face lattice representing certain combinatorial objects (e.g. ways to insert parentheses into a string). So I assumed that representing these structures as a face lattice was of some use.

But then people got interested in realizing these objects geometrically, and it turns out that, e.g. the associahedron can be realized in many ways. Was this surprising? Is there something to be learned from that fact? On the other hand, for the permutahedron the realization came probably first, so is there anything deep to learn from its combinatorial structure?

Further, there seem to exist connections to algebra, e.g. homotopy theory. I cannot wrap my head around these connections. For me, these polytopes are just further examples of polytopes, nothing else.

So what's up? Do they have some extremal properties? Are they especially symmetric (i.e. are they interesting for their symmetries)? Does the geometric point of view make apparent some hidden combinatorial properties of the underlying structures (e.g. the cyclohedron is said to be "useful in studying knot invariants")? What justifies this interest?

Philosophical questions deserve philosophical answers, so I am afraid no amount of references and specific results will probably satisfy you. Let me try to explain it in a somewhat generic way.

Think about it this way - why care about sequences like $$\{n!\}$$, Fibonacci or Catalan numbers? The honest answer is "because they come up all the time". Now, once you know these sequences, you may want to understand the underlying structures (permutations, trees, Dyck paths, triangulations, etc.) You may then want to understand connections between structures (e.g. bijections), algebraic or geometric interpretations (e.g. group representations, volumes of polytopes), etc. Once you have developed some kind of structures you may want to understand the relations between different structures, whether your bijections are structure-preserving, etc. That's how you develop the theory starting with just numbers!

In general, basic objects in combinatorics tend to lack structure. Adding structures is always welcome as they present a deeper understanding of the underlying objects (and sometimes even just numbers). It's what allows to employ and further develop tools from other parts of Combinatorics and other fields. This is the setup in which one can understand results such as Kuperberg's proof of the number of ASMs or the Adiprasito-Huh-Katz theorem, but it doesn't have to be so spectacular. Sometimes even a weak structure can lead to unexpected connections and generalizations unforeseen otherwise.

In summary, "these polytopes are just further examples of polytopes" is a misunderstanding of the context in the same way as Fibonacci and Catalan numbers are not "just numbers". Viewed in context, permutahedra and associahedra exhibit structures of combinatorial objects invisible otherwise.

• In "Lessons I Learned from Richard Stanley" (arxiv.org/abs/1501.00719) Jim Propp starts with "Two big ideas": "The biggest lesson I learned from Richard Stanley’s work is, combinatorial objects want to be partially ordered! ... A related lesson that Stanley has taught me is, combinatorial objects want to belong to polytopes!" – Sam Hopkins Jan 12 at 17:45
• Thank you! This answer really convinced me and I totally agree that "adding structure" is a good thing, especially in combinatorics. – M. Winter Jan 14 at 16:40

In my opinion there are two answers to this question.

The first is that these particular classes of polytopes have fascinating combinatorial properties and structure. Presumably you're aware of the work of Postnikov and others in this direction. In my view, and the view of many others, these properties make the polytopes worth studying in their own right.

The second is that these polytopes arise naturally in other contexts, e.g., as moment polytopes (images of certain manifolds/varieties under the moment map) and as weight polytopes (convex hulls of subsets of the weight lattice of certain Lie groups). Various geometric properties of the manifolds, and representation-theoretic properties of the group, can be reduced to combinatorial properties of the polytopes. For example, GKM theory tells you that (provided certain hypotheses are satisfied) you can define and calculate equivariant cohomology directly on the moment graph.

This of course is a very high-level answer. If you are wondering about whether certain specific combinatorial properties have geometric or representation-theoretic significance, then maybe you can state a more specific question.

• Good answer, yes, it’s worth pointing out the appearance of these polytopes in e.g. the book by Gelfand, Kapranov, Zelevinsky. – Sam Hopkins Jan 9 at 16:36

There are remarkable combinatorial formulas for the face numbers and the volumes (of certain geometric realizations of) of these polytopes and a more general family ("generalized permutohedra" a.k.a. "polymatroids") to which they belong. These numbers include classical sequences like the Eulerian numbers, Catalan numbers, $$(n+1)^{n-1}$$, etc. This is a major combinatorial interest in these polytopes.

Regarding the question about why geometric realizations are interesting in particular, note that to meaningfully talk about volume (and its relatives like discrete volume, i.e., number of lattice points, etc.) requires a particular geometric realization.

(Warning: "generalized permutohedra" and "generalized associahedra" are two different families of polytopes, despite the very similar names. "Generalized permutohedra" are obtained by deforming the normal fan of the regular permutohedron, i.e., sliding facets in and out along a normal vector. "Generalized associahedra" have to do with analogs of the associahedron in other Lie types.)

I'm not an expert, but perhaps this could help:

Hohlweg, Christophe. "Permutahedra and associahedra: Generalized associahedra from the geometry of finite reflection groups." arXiv:1112.3255 (2011):

"Permutahedra are a class of convex polytopes arising naturally from the study of finite reflection groups, while generalized associahedra are a class of polytopes indexed by finite reflection groups. We present the intimate links those two classes of polytopes share."

Fig.5.

This is one chapter in the following collection, which includes other possibly illuminating chapters:

Müller-Hoissen, Folkert, Jean Marcel Pallo, and Jim Stasheff, eds. Associahedra, Tamari lattices and related structures: Tamari memorial Festschrift. Vol. 299. Springer Science & Business Media, 2012. List of chapters with links.

Especially: Cesar Ceballos and Günter M. Ziegler: Realizing the Associahedron: Mysteries and Questions. arXiv. 2011.

They quote Haiman from 1984: "The associahedron is a mythical object"!

• I think it’s important to note that the major interest in generalized associahedra is their connection to cluster algebras. – Sam Hopkins Jan 9 at 16:27

The origins of associahedra go back to the thesis work in homotopy theory of Jim Stasheff in the early 1960's.

He did graduate work at Oxford, working with Ioan James, who in the mid 1950's had proved lots of beautiful theorems about the free associative topological monoid $$JX$$ generated by a based topological space $$X$$; in particular, showing that, when $$X$$ is connected, that $$JX$$ is homotopy equivalent to the free loopspace $$\Omega \Sigma X$$ generated by $$X$$.

He also did graduate work with John Moore at Princeton. Moore was part of the first generation to grow up thinking comfortably about both algebra and topology through the lens of category theory. For example, thinking hard about the associativity of the tensor product operation was already in the air, thanks to work of MacLane.

Stasheff's work channels the vibe of both of his advisors. He is answering the question: when is a topological space homotopy equivalent to the space of based loops on another space? Two examples are topological groups, and the spaces $$JX$$. These have strict associative multiplications, whereas, as everyone learns when they learn about the fundamental group, one makes some arbitrary choices when `adding' loops in a space, but then shows the choices are associative up to homotopy. Taking this last line seriously - remembering all basic choices of n-fold multiplications, and homotopies, and assembling them into (contractible) geometric objects - led Stasheff to his answer of the question. The family of objects are the associahedra.

Continuing through history, homotopy theorists fit the associahedra into their general theory of operads (named by J. Peter May) in the 60's and 70's. In the mid 1990's, these ideas became fashionable in algebra too, and have continued ever since.

Not surprising, objects arising from such a universal source (the associative law!) end up being interesting to study from many points of view, including combinatorics. But original and continuing interest comes from homotopy theory.

• IIRC, at the time of his thesis defense Stasheff had shown that the associahedron has the structure of a regular CW complex, and then Milnor (?) who was on his thesis defense panel asked about polytopiality, and then later showed Stasheff that it is in fact a polytope. Also, earlier Tamari had studied the 1-skeleton of the associahedron and its lattice structure. – Sam Hopkins Jan 12 at 17:36
• The history of the associahedra is discussed by Stasheff in the article "How I 'met' Dov Tamari" from the Tamari Memorial Volume mentioned in Joseph O'Rourke's answer. Stasheff gives credit for the independent discovery of the associahedra to Tamari, and in fact the latter included graphical depictions of the associahedra as convex polytopes already in his 1951 thesis. (Alas, this was in the unpublished part of his thesis.) – Noam Zeilberger Jan 14 at 21:37

Some of these polyhedra are of current interest to physicists—see for instance Nima Arkani-Hamed in the arXiv.

• It looked like "Bruno Harris" was part of a signature rather than part of the answer; since your name is automatically appended, I edited it out when I edited in a link to the arXiv search. Can you recommend any particular paper(s) by Arkani-Hamed? – LSpice Jan 14 at 20:53