# Guises of the Stasheff polytopes, associahedra for the Coxeter $A_n$ root system?

Richard Stanley keeps a famous running compilation of different guises of the celebrated Catalan numbers. The number of vertices of the associahedron is one instantiation among the multitude, and the associahedra themselves occur in many guises, so in some sense they are a multi-dimensional, geometric extension of the Catalans, that also pop up in a surprising variety of places (for a quick intro, see Jon McCammond, "Noncrossing partitions in surprising places").

Is there a compilation for the associahedra, like Richard Stanley's for the Catalans?

If not, what guises are you aware of?

Examples are relations to

1) Partial orderings of partial associations of a list

Reflected in the face structure of the associahedra, as described in McCammond's article.

2) Partition polynomials for Lagrange (compositional) inversion of functions or formal power series and so to iterated "Lie" derivatives

The partition polynomials are isomorphic to the face structure of the associahedra, see "The multiple facets of the associahedron" by J. Loday, and can be generated by an iterated (Lie) derivative $$[d/df(x)]^n$$, where $$f$$ is expressed in the indeterminates of a power series, or o.g.f., (OEIS-A133437, OEIS-A145271).

3) Classification of separation coordinates/variables for the Hamilton-Jacobi equations

In "Separation coordinates, moduli spaces and Stasheff polytopes" by K. Schobel and P. Veselov (nice figures!), the combinatorics of the polytopes tessellating the real version of the Deligne-Mumford-Knudsen moduli space $$\bar{M}_{0,n+2}(R)$$ of stable curves of genus zero with $$n + 2$$ marked points are used to describe the topology and algebraic geometry of the space of separation coordinates on the spheres $$S^n$$ and to classify the different canonical forms of these coordinates, or separation variables, for the Hamilton-Jacobi equation.

4) Diagonalization of convex polygons into non-overlapping convex sub-polygons

See the beautifully illustrated book Discrete and Computational Geometry (pg. 74) by S. Devadoss and J. O'Rourke. Also "Polygonal dissections and reversion of series" by A. Schuetz and G. Whieldon.

5) Secondary polytopes--convex hull of the area vectors of all triangulations of a convex polygon

See Devadoss and O'Rourke, pg. 79.

6) The Fulton-MacPherson compactification space of the configuration space of n particles colliding on an interval--truncated simplices

See D and O, pg. 241. Nested tubings also.

7) Deformation of bordered surfaces with marked points

See "Deformations of bordered surfaces and convex polytopes" by S. Devadoss, T. Heath, and W. Vipismikul.

8) Cluster A algebras and coordinates for scattering amplitudes

See "Cluster polylogarithms for scattering amplitudes" by J. Golden, M. Paulos, M. Spradlin, and A. Vlolovich.

9) Schroeder lattice paths (marked Dyck paths, OEIS A126216)

Enumerated by f-vectors of the associahedra (Narayana * Pascal, lower triangular matrices).

10) Solutions to the inviscid Hopf-Burgers equation

See "Toric topology of the Stasheff polytopes" by V. Buchstaber and also MO-Q145555.

11) Coinverse (antipode) for a Hopf algebra

Analogous to the Faa di Bruno Hopf algebra, but represented in the indeterminates of a power series/ordinary generating function rather than those of a Taylor series/exponential generating function. Then the coproduct is related to Lah partition polynomials rather than Bell partition polynomials and the antipode, to Lagrange inversion/series reversion for o.g.f.s and therefore to associahedra rather than e.g.f.s. and Whitehouse simplicial complexes. For the usual e.g.f. formulation of the Faa di Bruno Hopf algebra, see Quantum Field Theory II Quantum Electrodynamics (pg. 136) by E. Zeidler or "Combinatorial Hopf algebras in quantum field theory I" by H. Figueroa and J. Gracia-Bondi.

(Each topic could be elaborated upon. The links in the OEIS refer to algebras I'm not comfortable with. Please feel free to do so in an answer.)

I know several examples, the third being the most recent I've come across, but there are others who frequent this site who can easily state more accurately and succinctly than I other connections of the associahedra to operads, spaces homotopically equivalent to loop spaces, trees, dendriform algebra, moduli spaces, ... .

• The simplicial dual and the h-vectors also pop up in interesting places, and if you re-scale the indeterminates of the o.g.f. for the Lagrange inversion to generate an e.g.f. formulation, the Whitehouse simplicial complexes, tropical Grassmannians, and phylogenetic trees sprout up (expressing the inversion in terms of the indeterminates of the reciprocal of the function introduces the Narayana h-vectors), so it's a skip and a hopf from the associahedra to other complexes and classic number arrays. – Tom Copeland Oct 20 '14 at 5:50
• mathoverflow.net/questions/6373/… – Tom Copeland Dec 12 '14 at 4:17
• More: "The brick polytopes of a sorting network" by Pilaud and Santos (arxiv.org/abs/1103.2731) and " Noncrossing hypertrees" by McCammond . – Tom Copeland May 17 '17 at 23:52
• "Cluster algebras: an introduction" by Williams (pg. 7) arxiv.org/abs/1212.6263 – Tom Copeland Jul 19 '17 at 13:58
• See Theorem 16 of math.mit.edu/~rstan/papers/parkpoly.pdf for a connection with the so-called Pitman-Stanley polytope. – Richard Stanley Nov 12 '18 at 22:13

If $Q$ is the quiver $A_n$ with linear orientation, then the Stasheff associahedron appears as the polytope with vertices the basic tilting $kQ$-modules and faces the faithful basic exceptional $kQ$-modules. The partial order on faces is defined by $M \leq N$ whenever $N$ is a a direct summand of $M$. This gives a poset isomorphic to the one in your first example.

References:

Buan, Aslak Bakke; Krause, Henning. Tilting and cotilting for quivers of type $\tilde A_n$, section 3 and appendix A.

Buan, Aslak Bakke; Marsh, Robert; Reineke, Markus; Reiten, Idun; Todorov, Gordana. Tilting theory and cluster combinatorics, section 4.

• The cluster story continues from there to combinatorics in front.math.ucdavis.edu/1108.1776 "Subword complexes, cluster complexes, and generalized multi-associahedra" and then to geometry in front.math.ucdavis.edu/1404.4671 "Brick manifolds and toric varieties of brick polytopes". – Allen Knutson Oct 19 '14 at 23:20
• I don't know much more than what you wrote, that the associative operad is Koszul self-dual. I wonder if this could be read off as a combinatorial property of the associahedra? It's better to let someone else answer this. – Dag Oskar Madsen Oct 20 '14 at 10:03
• There is natural bijection between rooted planar binary trees and tilting modules for the quivers if I read Chapoton correctly. – Tom Copeland Dec 19 '14 at 11:44
• @AllenKnutson : and there is even more to that, I am happy to say: arxiv.org/abs/1510.03261 . – Vladimir Dotsenko Oct 13 '15 at 7:10
• The link in the previous comment is to "Toric varieties of Loday's associahedra and noncommutative cohomological field theories" by Dotsenko, Shadrin, and Vallette. – Tom Copeland Oct 5 '19 at 21:26

One direct way the associahedra give rise to a generalization of Catalan numbers is perhaps worth mentioning. While the latter are $\frac{(2n)!}{(n+1)!n!}$, the number of faces of shape $S_1^{n_1}\times S_2^{n_2}\times S_3^{n_3}\times\cdots$ in $S_n:=$ the $n-1$-dimensional Stasheff polytope, where $n=n_1+n_2+n_3+...$, is equal to $\frac{(2n_1+3n_2+4n_3+...)!}{(n_1+2n_2+3n_3+...+1)!n_1!n_2!n_3!\cdots}$.

The first appearance of thеse numbers that I know I learned from the answer by Ira Gessel to the question "MultiCatalan numbers" - it seems to be W. T. Tutte, The number of planted plane trees with a given partition. Amer. Math. Monthly 71 (1964) 272–277 (although there is no mention of polytopes there).

Later - as suggested by Tom Copeland I am adding one reference from one of my comments here too: M. Kapranov and M. Saito "Hidden Stasheff polytopes in algebraic K-theory and in the space of Morse functions" (K-theory preprint archive, May 1997) contains an intriguing and, as far as I know, still not fully understood connection between associahedra and Steinberg relations. Briefly, the key relation $[e_{ij}(a),e_{jk}(b)]=e_{ik}(ab)$ appears as a pentagon in a cell complex encoding homologies of general linear groups; higher relations similarly contributing to higher homologies can be arranged into Stasheff polytopes. That paper also describes appearance of associahedra encoding catastrophes leading to interactions between critical points of generic Morse functions.

• Given Cayley's familiarity with Catalans as a generating series for enumerating certain forests of trees and the dissections of polygons, his use of analytic trees to model iterated derivatives (operandators), and his, Sylvester's, and Graves' work on normal ordering of differential operators, it's surprising that he didn't discover these numbers through the connection between iterated derivatives and Lagrange inversion, which he frequently used. (Or maybe he did.) – Tom Copeland Oct 20 '14 at 13:59
• @TomCopeland Btw I was always puzzled (and disappointed) by the fact that none of the handbooks like Abramowitz & Stegun, Gradshtejn & Ryzhik, Janke-Emde-Lösch, Dwight, etc. mention any explicit formulas for coefficients of formal series reverses (or inverses, logarithms, exponents, composites, etc. for that matter) – მამუკა ჯიბლაძე Oct 20 '14 at 14:30
• Composites are noted in A & S (see partitions), but generally you are right. Around 1857, Graves wrote down the relation between iterated derivatives and inversion (no expansion?). Maybe it wasn't until Boltzmann intro. stat mech and Feynman, his diagrams that combinatorics really started to be noticed in physics (aside from the dalliance with knots and vortices/atoms) whereas special fcts. had been around in a central role. When and why Bruno-like partitions nudged their way onto the stage, I don'know (maybe cumulants and cluster expansions in stat mech), but they are in A&S. – Tom Copeland Oct 20 '14 at 16:05
• The Kirkman(1857)-Cayley(1890) numbers in fact generate the number of faces of the associahedra, what you call the multiCatalan numbers. – Tom Copeland Oct 24 '14 at 9:34
• Newton himself derived the formal inverse of power series (o.g.f.s), and, therefore, at least, the first few of the refined face polynomials of the associahedra. I don't know if he had a general formula for the coefficients, but he was a master at computation and binomial coefficients, so I wouldn't bet against it. – Tom Copeland Nov 20 '17 at 18:02

From "Scattering Forms and the Positive Geometry of Kinematics, Color and the Worldsheet" (arxiv) by Nima Arkani-Hamed, Yuntao Bai, Song He, and Gongwang Yan:

The search for a theory of the S-Matrix has revealed surprising geometric structures underlying amplitudes ranging from the worldsheet to the amplituhedron, but these are all geometries in auxiliary spaces as opposed to kinematic space where amplitudes live. In this paper, we propose a novel geometric understanding of amplitudes for a large class of theories. The key idea is to think of amplitudes not as functions, but rather as differential forms on kinematic space. We explore the resulting picture for a wide range of massless theories in general spacetime dimensions. For the bi-adjoint $$\phi~^3$$ in scalar theory, we establish a direct connection between its “scattering form” and a classic polytope—the associahedron—known to mathematicians since the 1960’s. We find an associahedron living naturally in kinematic space, and the tree level amplitude is simply the “canonical form” associated with this “positive geometry”. Fundamental physical properties such as locality and unitarity, as well as novel “soft” limits, are fully determined by the combinatorial geometry of this polytope. Furthermore, the moduli space for the open string worldsheet has also long been recognized as an associahedron. We show that the scattering equations act as a diffeomorphism between the interior of this old “worldsheet associahedron” and the new “kinematic associahedron”, providing a geometric interpretation and simple conceptual derivation of the bi-adjoint CHY formula.