Why are we interested in permutahedra, associahedra, cyclohedra, ...?

Question

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

• permutahedra,
• associahedra,
• cyclohedra,
• ...

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.)

Answer 5

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"!

Answer 6

If I were an orthodox Bourbakist, I would say the polytopes per se are of no interest, but I'm not. The geometric enumerative combinatorics of the faces of the permuto/permutahedra and the associahedra respectively reflect the algebra of multiplicative and compositional inversion of formal power series, and I find that alone fascinating.

But, how useful are the geometric realizations of the combinatorics of these relations?

First consider the algebraic equation of a circle and the geometric rep. Through which rep. is it easier to discern the possible number of intersections of two circles of different radii, not given their locations in a plane?

Now consider two particles traveling on two circles, one on each. The geometry of the intersections tells us a lot about the possible trajectories of collisions of the particles and would guide us in developing a program to calculate and depict them.

Ramp up your knowledge of algebra, analysis, geometry, and physics, and now you are prepared to understand "Combinatorics and Topology of Kawai–Lewellen–Tye Relations" by Sebastian Mizera. The abstract:

We revisit the relations between open and closed string scattering amplitudes discovered by Kawai, Lewellen, and Tye (KLT). We show that they emerge from the underlying algebro-topological identities known as the twisted period relations. In order to do so, we formulate tree-level string theory amplitudes in the language of twisted de Rham theory. There, open string amplitudes are understood as pairings between twisted cycles and cocycles. Similarly, closed string amplitudes are given as a pairing between two twisted cocycles. Finally, objects relating the two types of string amplitudes are the $\alpha_0$-corrected bi-adjoint scalar amplitudes recently defined by the author 1. We show that they naturally arise as intersection numbers of twisted cycles. In this work we focus on the combinatorial and topological description of twisted cycles relevant for string theory amplitudes. In this setting, each twisted cycle is a polytope, known in combinatorics as the associahedron, together with an additional structure encoding monodromy properties of string integrals. In fact, this additional structure is given by higher-dimensional generalizations of the Pochhammer contour. An open string amplitude is then computed as an integral of a logarithmic form over an associahedron. We show that the inverse of the KLT kernel can be calculated from the knowledge of how pairs of associahedra intersect one another in the moduli space. In the field theory limit, contributions from these intersections localize to vertices of the associahedra, giving rise to the bi-adjoint scalar partial amplitudes.

(For more on associahedra and scattering amplitudes in quantum physics, just google the terms. See also this MO-Q and the attendant comments and links.)

Conceivably, the permutohedra might prove useful since they can be deformed into associahedra. Analogously, conic sections other than the circle are important in understanding gravity and collisions of asteroids with planets as well as SL2 transformations. Good to have diverse reps shedding different light on mathematical and physical relations, in general.

For connections to extremal properties, see the Aquiar and Ardila ref in https://oeis.org/A133314 for permutahedra (also for multiplicative inversion of power series, surjective mappings, the inversion of modified Pascal matrices and other matrices derived from infinitesimal generators, lattice paths, the formalism of Appell polynomials related to Weyl algebras, quantum field theory) and https://oeis.org/A133437 for the associahedra (compositional inversion, quantum physics, lattice paths, and a slew of connections to other diverse geometric / combinatorial structures).

Answer 7

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