18
$\begingroup$

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 [A126216] = [A001263][A007318]= Narayana * Pascal $= [N][P]$ as 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.

12) The shifted reciprocal of the o.g.f. of the refined Euler characteristic partition polynomials of the associahedra give the formal free cumulants of free probability theory, and the polynomials are proportional to a partial derivative of the free cumulants (added 1/20/22)

See the MO-Q "Combinatorics for the action of Virasoro / Kac–Schwarz operators: partition polynomials of free probability theory".

13) The associahedra and noncrossing partitions are dual geometric and analytic constructs (Added 7/19/2022)

The signed generalization/refinement of item 9 above is $[A] = [N][R] =$ [A133437] = [A111785] = [A134264][signed A263633], where, e.g., $[R][a]$ represents substitution of the infinite set of indeterminates $(a_1,a_2,...)$ for those of the reciprocal partition polynomials (for o.g.f.s) defined by $x/f(x) = 1/(1+c_1x+c_2x^2 + \cdots) = R_0 + R_1(c_1) x + R_2(c_1,c_2) x^2 + \cdots$; the set of partition polynomials of $[A]$ are the refined Euler characteristic polynomials for the associahedra; and $[N]$, the refined Narayana, or noncrossing partition, polynomials. (The indeterminates and partition polynomials of the associahedra polynomials A1334347 must be re-indexed, i.e., shifted by -1, with (1') = 1.) Note $[R]^2 =[I]=[A]^2$ is the identity transformation under indeterminate substitution/composition, so also $[A][R] = [N]$.

In addition, $[I]=[A][R][R][A] = [N][R][A] = [R][A][A][R] = [R][A][N] $ implies $[R][A] = [N]^{-1}$, the inverse of $[N]$. The pair of inverses define the free moments and cumulants of free probability theory in terms of each other, so we can connect the associahedra to free probability as well along with its connections to random matrix theory and quantum fields.

The e.g.f. equivalent is $[L] = [E][P]$, where $[L]$ is the set of classic Lagrange inversion polynomials A134685, associated with weighted phylogenetic trees; $[E]$, the refined Eulerian polynomials A145271; and $[P]$, the refined Euler characteristic polynomials $P_n(d_1,...,d_n)$ A133314 of the permutahedra, giving the Taylor series coefficients of the reciprocal $1/h(x)$ of the e.g.f. $h(x) = 1 + d_1 x +d_2 \frac{x^2}{2!}+\cdots.$ We have a dual set of generators $[E]$ and $[E]^{-1}$ for an infinite group as well since $[L]^2 = [I] = [P]^2$.

The two sets of compositional inversion polynomials $[L]$ and $[A]$ are related by a simple scaling of the indeterminates by the factorials just as formal e.g.f.s are related to formal o.g.f.s--a simple Borel-Laplace transform term by term--and so are the sets of multiplicative inversion polynomials $[R]$ and $[P]$ .

From the four sets of partition polynomials $[A]$,$[L]$,$[N]$, and $[E]$ issue compositional inverses of series while from $[R]$ and $[P]$, multiplicative inverses. This equivalence is the integrating thread of a tapestry of geometric/topological and algebraic/analytic constructs from polytopes and trees to moduli spaces, punctured Riemann surfaces, and characteristic classes to quadratic operads and Lie derivatives/infinitesimal generators (and, naturally, up on the tapestry is quantum physics, e.g., see this MO-Q).


(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, ... .

$\endgroup$
49
  • $\begingroup$ 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. $\endgroup$ Oct 20, 2014 at 5:50
  • $\begingroup$ mathoverflow.net/questions/6373/… $\endgroup$ Dec 12, 2014 at 4:17
  • $\begingroup$ More: "The brick polytopes of a sorting network" by Pilaud and Santos (arxiv.org/abs/1103.2731) and " Noncrossing hypertrees" by McCammond . $\endgroup$ May 17, 2017 at 23:52
  • $\begingroup$ "Cluster algebras: an introduction" by Williams (pg. 7) arxiv.org/abs/1212.6263 $\endgroup$ Jul 19, 2017 at 13:58
  • 1
    $\begingroup$ See Theorem 16 of math.mit.edu/~rstan/papers/parkpoly.pdf for a connection with the so-called Pitman-Stanley polytope. $\endgroup$ Nov 12, 2018 at 22:13

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
6
  • 3
    $\begingroup$ 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". $\endgroup$ Oct 19, 2014 at 23:20
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 20, 2014 at 10:03
  • $\begingroup$ There is natural bijection between rooted planar binary trees and tilting modules for the quivers if I read Chapoton correctly. $\endgroup$ Dec 19, 2014 at 11:44
  • $\begingroup$ @AllenKnutson : and there is even more to that, I am happy to say: arxiv.org/abs/1510.03261 . $\endgroup$ Oct 13, 2015 at 7:10
  • $\begingroup$ The link in the previous comment is to "Toric varieties of Loday's associahedra and noncommutative cohomological field theories" by Dotsenko, Shadrin, and Vallette. $\endgroup$ Oct 5, 2019 at 21:26
2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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.) $\endgroup$ Oct 20, 2014 at 13:59
  • $\begingroup$ @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) $\endgroup$ Oct 20, 2014 at 14:30
  • $\begingroup$ 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. $\endgroup$ Oct 20, 2014 at 16:05
  • 1
    $\begingroup$ The Kirkman(1857)-Cayley(1890) numbers in fact generate the number of faces of the associahedra, what you call the multiCatalan numbers. $\endgroup$ Oct 24, 2014 at 9:34
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 20, 2017 at 18:02
1
$\begingroup$

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.

$\endgroup$
10

Your Answer

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