More Secrets of the Associahedra

January 25, 2018

Posted by John Baez

$MathML-enabled post (click for more details).$

The associahedra are wonderful things discovered by Jim Stasheff around 1963 but even earlier by Dov Tamari in his thesis. They hold the keys to understanding ‘associativity up to coherent homotopy’ in exquisite combinatorial detail.

But do they still hold more secrets? I think so!

$MathML-enabled post (click for more details).$

Of course, what’s a secret to me may be well-known and boring to you. But this result by Marcelo Aguiar and Federico Ardilla intrigues and excites me!

Take a formal power series like this:

$C(x) = x + c_1 x^2 + c_2 x^3 + \cdots$

If you take its right inverse under composition, meaning the power series $D$ with

$C(D(x)) = x$

you get another formal power series of the same type:

$D(x) = x + d_1 x^2 + d_2 x^3 + \cdots$

How are the $d_n$ related to the $c_n$ ? Do some calculations:

$d_1 = - c_1$

$d_2 = -c_2 + 2 c_1^2$

$d_3 = -c_3 + 5 c_2 c_1 - 5 c_1^3$

$d_4 = -c_4 + 6 c_3 c_1 + 3 c_2^2 - 21 c_2 c_1^2 + 14 c_1^4$

What are these coefficients? They’re controlled by the associahedra! For example, the 3-dimensional associahedron looks like this:

It has:

• 1 three-dimensional face,

• 6 pentagonal and 3 square faces,

• 21 edges, and

• 14 vertices.

So, if we call the $n$ -dimensional associahedron ${\mathbf{c}}_{n-1}$ , then $\mathbf{c}_1$ is a point, $\mathbf{c}_2$ is an interval, $\mathbf{c}_3$ is a pentagon, and the 3d associahedron ${\mathbf{c}}_4$ has

• 1 face shaped like ${\mathbf{c}}_4$ ,

• 6 faces shaped like ${\mathbf{c}}_3 \times \mathbf{c}_1$ and 3 faces shaped like ${\mathbf{c}}_2 \times {\mathbf{c}}_2$ ,

• 21 faces shaped like ${\mathbf{c}}_2 \times \mathbf{c}_1 \times \mathbf{c}_1$ , and

• 14 faces shaped like $\mathbf{c}_1 \times \mathbf{c}_1 \times \mathbf{c}_1 \times \mathbf{c}_1$ .

All this face information is packed into the formula we saw:

$d_4 = -c_4 + 6 c_3 c_1 + 3 c_2^2 - 21 c_2 c_1^2 + 14 c_1^4$

Why is this happening, and what can we do with it? I don’t know! I should start by reading this:

Marcelo Aguiar, Federico Ardila, Hopf monoids and generalized permutahedra.

They have very similar results for permutahedra and other delicious polytopes. The permutahedra show up when you invert formal power series with respect to multiplication, rather than composition!

Posted at January 25, 2018 7:05 PM UTC

TrackBack URL for this Entry: https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3011

41 Comments & 0 Trackbacks

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

John, thanks for blogging about this! I also found this result (which was certainly new to me) to be very exciting and would love to dig into its proof.

Federico Ardila just delivered an invited address at the Joint Mathematics Meetings about this work. He previewed his talk with a two-page teaser Algebraic Structures on Polytopes.

And while I’m linking to things Federico has written in the Notices of the AMS, everyone should read Todos Cuentan: Cultivating Diversity in Combinatorics.

Posted by: Emily Riehl on January 25, 2018 11:53 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

I wasn’t at the JMM, but I bumped into the January Notices of the AMS, which is where I learned about this.

It should be really fun to categorify formal power series by taking polytopes, or more generally subsets of $\mathbb{R}^n$ generated by union and set-theoretic difference from polytopes, as coefficients. The Euler–Schanuel characteristic lets us turn any such set into an integer. It may be that we can prove some of the Aguiar–Ardila identities at the categorified level by exhibiting a homotopy equivalence (or something roughly like that!) between two subsets of $\mathbb{R}^\infty$ that are countable unions of subsets of the above form. Jim Propp has done a lot of things like this, such as giving a new proof that

$\displaystyle{\binom{1/2}{2} = -\frac{1}{8}}$

Posted by: John Baez on January 26, 2018 1:06 AM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

I’m intrigued by the identity

(1)

\displaystyle{\binom{1/2}{2} = -\frac{1}{8}}.

Is there a more elementary interpretation/proof which doesn’t depend on categorified combinatorics?

Posted by: Arun Debray on January 26, 2018 3:55 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

I was sort of puzzled by this as well, although without being puzzled enough to click John’s link to Jim Propp’s paper. I’d take

$\binom{x}{k} = \frac{x(x - 1)\cdots(x - k + 1)}{k!}$

as the definition of $\binom{x}{k}$ , for real $x$ and natural numbers $k$ . In that case, the identity is trivial. But obviously there’s something interesting going on beyond this!

Posted by: Tom Leinster on January 26, 2018 4:23 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

Here’s my quick reading of the results in the Propp paper that John is talking about.

The notion of cardinality for finite sets is something we are very familiar with and has various nice properties.

For instance

$\#(X \times Y)= \#(X) \times \#(Y).$

If we write $X^Y$ for the set of maps from $Y$ to $X$ then we have

$\#(X^Y)=(\# (X))^{\#(Y)}.$

And if we write $\binom{X}{n}$ for the set of $n$ element subsets of $X$ then

$\#\binom{X}{n}=\binom{{\#} X}{n} .$

In this paper Propp gives some examples which ‘generalize’ these results. He works with a class of subsets of $\mathbb{R}^n$ which he calls ‘polyhedral sets’ which includes finite sets and defines an ‘Euler measure’ $\chi$ which extends the cardinality function and satisfies inclusion/exclusion relation:

$\chi(X\cup Y)=\chi (X) +\chi (Y) - \chi(X\cap Y).$

He shows suitable notions of ‘set of maps’ and ‘set of $n$ -element subsets’ can be defined in this polyhedral setting.

Then he takes $B$ to be the two element set $\{0,1\}$ so $\chi (B) = 2$ . And takes $A$ to be the open interval $(0,1)$ so that $\chi(A)= -1$ . [This Euler measure is not a homotopy invariant! We do have $\chi(closed\,\,interval) =1$ and the open interval result follows from the inclusion/exclusion relation.]

He then shows that

$\chi(B^A)= 1/2 = 2^{-1}= \chi(B)^{\chi(A)}$

and that

$\chi\binom{B^A}{2} = -1/8 =\binom{1/2}{2} =\binom{\chi(B^A)}{2}.$

So I would say he gives an interpretation of that identity, rather than a new proof!

Posted by: Simon Willerton on January 26, 2018 6:16 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

My colleague John Greenlees came back from the Joint Mathematical Meeting in San Diego quite excited about this, but when he started telling me about it I realised that, by strange coincidence, I’d come across it the day before in an article in Quanta Magazine.

Posted by: Simon Willerton on January 26, 2018 6:28 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

So, my impression was that compositional inverses of formal power series are related to taking Koszul duals of operads, in the same way that multiplicative inverses of formal power series are related to taking Koszul duals of algebras. Does anyone know a reference where a story like this is told? I don’t remember where I picked it up.

Posted by: Qiaochu Yuan on January 26, 2018 12:16 AM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

I’ve not looked at this for a very long time, but do you mean Theorem (3.3.2) of Ginzburg-Kapranov?

Koszul duality for operads, Duke Math. J. Volume 76, Number 1 (1994), 203-272. (arxiv:0709.1228)

Posted by: Simon Willerton on January 26, 2018 7:40 AM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

Not a reference, but here’s a sketch of the idea.

I think you want Koszul duality for non-symmetric operads (because we’re using rational generating functions). If you have a $dg$ operad $P$ , then for its its Koszul dual cooperad $P^!$ , we have that $P^! \circ P$ admits a differential which is exact except in homological degree $0$ and grading degree $1$ . Taking euler-characteristics, we see that $\chi(P)(t)$ and $\chi(P^!)(t)$ are inverses.

You can a construct a model for $P^!$ by a “bar construction”, which involves taking the free nonsymmetric cooperad of $P$ and equipping it with a differential. Concretely this involves summing over all planar trees weighted by the operations of $P$ , which starts to look a lot like associahedra. Take the euler-characterstic, again and the formula for $\chi(P^!)(t) = \chi(P)^{-1} (t)$ pops out!

Posted by: Phil Tosteson on January 26, 2018 5:39 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

Looks like Proposition 13.11.7 of Loday and Valette’s book Algebraic Operads gives the same argument.

Maybe it’s be more geometrically suggestive to interpret the associahedron as the “moduli space of metric planar graphs”, and the “bar construction” as computing the cohomology of a constructible sheaf on this space using the canonical CW-structure. Ginzburg and Kapranov do the analogous thing for symmetric operads.

Posted by: Phil Tosteson on January 26, 2018 10:55 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

Well, one place you could very easily have picked it up is on MathOverflow: https://mathoverflow.net/questions/194888/inversion-koszul-duality-combinatorics-and-geometry

Posted by: Tom Copeland on March 10, 2018 9:08 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

Well, one place you could very easily have picked it up is on MathOverflow: https://mathoverflow.net/questions/194888/inversion-koszul-duality-combinatorics-and-geometry

Posted by: Tom Copeland on March 10, 2018 9:13 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

The associahedra have also recently appeared in relation to the amplituhedron, in a preprint by Nima Arkani-Hamed, Yuntao Bai, Song He, and Gongwang Yan. From the abstract:

“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 is to think of amplitudes as differential forms directly on kinematic space. We explore this picture for a wide range of massless theories in general spacetime dimensions. For the bi-adjoint cubic scalar, 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 amplitude is simply the canonical form associated with this positive geometry.”

Posted by: stefan on January 26, 2018 8:57 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

I think there is a small typo in the formula for $d_3$ : shouldn’t that be $d_3 = -c_3 + 5 c_2 c_1 - 5 c_1^3$ , since the pentagon has one face, five edges, and five points?

That is a really intriguing fact, though. The Aguiar & Ardilla paper also includes these great lines in the acknowledgments section:

We do not thank the Portland, OR thieves who set the project back in 2013 by stealing a folder containing five years of work: results, proofs, writeups, pictures, examples, and counterexamples. We do thank them for not publishing our results in their name.

By way of trivia, I noticed something surprisingly similar mentioned in the acknowledgments section + footnotes of an old paper by Tamari on The Associativity Problem for Monoids and the Word Problem for Semigroups and Groups (1973):

This paper owes its origin to an attempt to freely reconstruct and to update, as far as feasible, work lost in 1962.* […]

*See historical remark in footnote preceding page.

[preceding page]*A handbag containing manuscripts and documents of the author disappeared in the harbor of Haifa, Israel, September 9, 1962. In spite of rewards offered it was never recovered.

Apparently the study of the associahedra is fraught with danger!

Posted by: Noam Zeilberger on January 28, 2018 2:26 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

Noam wrote:

I think there is a small typo in the formula for $d_3$ [….]

Thanks! I’m terrible at copying formulas unless I’m in the process of figuring something out: I get bored, make typos, and fail to catch them. I tried to catch all my typos here — honest! But I didn’t bother to think “hmm, a pentagon doesn’t have 6 vertices”. I was too busy thinking about how to explain this stuff.

I haven’t had time to look at the Aguiar–Ardilla paper. Thanks for pointing out that remarkable acknowledgment, and its eerie similarity to Tamari’s. If I ever work on this topic I’ll hire an armed guard.

It reminds me very slightly of an incident I recently learned concerning Otto Nikodym, the guy who helped invent the Radon–Nikodym theorem.

Nikodym wrote a lot of books, but three of his book manuscripts — the second volume of Theory of Tensors and two volumes of his Mechanics — disappeared during World War II. Years of work lost! But when he first heard this, he coolly responded:

In that case I will not have to correct the galley-proofs.

When asked if he would like to write these books again, he answered:

There are so many new problems that I cannot spend more time on those that I have already finished.

Posted by: John Baez on January 28, 2018 5:29 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

Given all these thefts, it almost seems that Stasheff is to blame. But that would be guilt by association.

Posted by: John Baez on January 29, 2018 7:39 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

Ba dum cha!

Posted by: Simon Willerton on January 29, 2018 10:43 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

This blew my mind! I had to spend some time thinking about how the associahedra could possibly be encoded in power-series arithmetic. After some thought, I don’t find it so unsettling, just cool.

The relationship reminds me of the fact that the coefficients of $(x+y)^n$ give the ways of choosing $k$ -element subsets from among $n$ -elements. Of course this is so basic that we call both of these things “binomial coefficients”, but it is an initially surprising connection. After a brief skim of the Aguiar-Ardilla paper, I guess it looks like the same sort of thing. I’d love to know if others have that impression, or if there is another conceptual explanation for the link.

Posted by: Niles Johnson on January 28, 2018 8:29 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

I have a nice story about

$\displaystyle{ (x + y)^n = \sum_{k = 0}^n \binom{n}{k} x^k y^{n-k} }$

$x$ and $y$ are finite sets. The equals sign means we have a natural isomorphism. Addition means coproduct. $a^b$ is the set of maps from the finite set $b$ to the finite set $a$ . $\binom{a}{k}$ is the set of subsets of $a$ of cardinality $k$ .

So: to choose a function from an ordinal $n$ to the disjoint union $x + y$ , we choose an ordinal $k$ less than or equal to $n$ , then choose a $k$ -element subset of $n$ , and then choose a map from $k$ to $x$ and a map from $n-k$ to $y$ .

So, the formula has turned into a self-evident fact about finite sets that explains why the formula is true for natural numbers. Once you see it this way, it’s impossible to forget.

(Extra credit: say it all without mentioning ordinals, which is a trick for taking a skeleton of the category of finite sets.)

I’d like something equally cogent for the associahedron identity of Aguiar and Ardilla. However, I suspect this will require a more homotopical viewpoint. Power series

$\sum_{n = 0}^\infty a_n x^n , \qquad a_n \in \mathbb{R}$

are typically about functors from the groupoid of totally ordered finite sets to sets. Composition of such power series describes the ‘substitution’ tensor product in this functor category. Monoids in this category with its substitution tensor product are non-symmetric operads. But when we get negative coefficients $a_n$ , we must be dealing with functors from the groupoid of totally ordered finite sets to something like chain complexes or well-behaved spaces, which have an ‘Euler characteristic’. This is why I think Phil Toleston is on the right track.

Of course I could break down and read Aguiar and Ardilla’s paper, but that would be cheating!

Posted by: John Baez on January 28, 2018 9:29 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

No offense, but somehow I don’t like the way you explained the binomial theorem: ordinals seem so irrelevant here that it seems a sin to mention them at all!

Let $x, y, n$ denote finite sets. A function $f: n \to x + y$ determines and is uniquely determined by three data: (1) a subset $f^{-1}(x) \subseteq n$ , of some cardinality $k$ between $0$ and $n$ inclusive (a set of $n$ choose $k$ possibilities), (2) the restriction of $f$ to a function $f^{-1}(x) \to x$ (a set of $x^k$ possibilities), and (3) the restriction $f^{-1}(y) \to y$ (a set of $y^{n-k}$ possibilities).

Structurally, the idea of decomposing a function $f: n \to x + y$ into two functions is connected to the fact that the category of finite sets is an extensive category, i.e., taking disjoint sums yields a categorical equivalence

$+: \mathbf{Fin}/x \times \mathbf{Fin}/y \to \mathbf{Fin}/x + y.$

As an aside (and as you know John), there’s a nice $q$ -binomial theorem which can be interpreted structurally in terms of maps between vector spaces over the finite field $\mathbb{F}_q$ .

Posted by: Todd Trimble on January 29, 2018 1:05 AM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

I hope you noticed I said:

(Extra credit: say it all without mentioning ordinals, which is a trick for taking a skeleton of the category of finite sets.)

Somehow you managed to do this problem in a way that made me feel ashamed of even assigning it.

Posted by: John Baez on January 29, 2018 2:00 AM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

I noticed, but I didn’t mean to make you feel bad. :-) I myself find things like this sort of delightful.

Related in spirit is a more or less ordinal-free explanation of the formula $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ for $0 \leq k \leq n$ , where we define the left side to be the number of $k$ -element subsets of an $n$ -element set. Pick any old $k$ -element subset $S$ of a finite subset $n$ . Then a permutation $f: n \to n$ determines and is determined by three data: (1) a $k$ -element subset $f(S)$ (a set of $\binom{n}{k}$ possibilities), (2) a bijection $S \to f(S)$ (a set of $k!$ possibilities), and (3) a bijection $n \setminus S \to n \setminus f(S)$ (a set of $(n-k)!$ possibilities). We have thus shown

$n! = \binom{n}{k} k! (n-k)!.$

These days I’m mentoring a budding mathematician currently in the 8th grade, where we’re discussing things like this.

Posted by: Todd Trimble on January 29, 2018 2:59 AM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

I usually think of $n!$ as the group of permutations of a finite set that happens to be called $n$ . If we write $n$ as a coproduct $k + (n-k)$ , then we get an inclusion of groups

$k! \times (n-k)! \hookrightarrow n!$

and the resulting subgroup of $n!$ is the stabilizer of $k \subseteq n$ . So, the quotient of $n!$ by this subgroup is isomorphic to the collection of all subsets of $n$ isomorphic to $k$ , which I call $\binom{n}{k}$ . So,

$\binom{n}{k} \cong \frac{n!}{k! \times (n-k)!}$

Posted by: John Baez on January 29, 2018 3:09 AM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

I have a slightly bad conscience about deflecting attention from the more interesting things being discussed in this post, but I guess I’ll go ahead and respond.

The proof you gave and the proof I gave for $\binom{n}{k} = \frac{n!}{k! \cdot (n-k)!}$ seem quite similar. My own was suitable for my $8^{th}$ -grader since it doesn’t refer to group theory or an action of the symmetric group on a power set, and I had also wanted to bring out an analogy between that proof and the proof I outlined for the binomial theorem: in both cases, a function is reconstituted from three data involving a pair of complementary subsets and the restriction of the function to each of those subsets. I have a vague inner urge to coalesce those two proofs into one, somehow.

Another thought occurs to me here, that the binomial theorem should have the same formal content as the exponential law $\exp(X + Y) = \exp(X) \cdot \exp(Y)$ . At least that’s true at the decategorified level: in order to see this as an identity between formal power series, one rearranges some sums and invokes the binomial theorem. Meanwhile, there’s a very nice categorified explanation of the exponential identity: $\exp(X)$ is interpreted as the free commutative monoid on $X$ . This functor $\exp: \mathbf{Set} \to \mathbf{CMon}$ , being left adjoint to the forgetful functor, preserves coproducts as left adjoints do. But the coproduct of commutative monoids is, at the underlying set level, given by cartesian product. QED.

What I’m vaguely hoping is to flush out a proof of the structural binomial theorem, maybe also the formula for $n$ choose $k$ , hiding within the categorical argument of the preceding paragraph.

Posted by: Todd Trimble on January 30, 2018 1:15 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

I like your way of thinking about

$\exp(x+y) = \exp(x) \exp(y)$

based on treating $\exp(x)$ as the free commutative monoid on $x$ . To get the binomial theorem from this identity I seem to want the identity

$\exp(x) = 1 + x + \frac{x^2}{2!} + \cdots$

I believe this sort of formula for the free commutative monoid on $x$ works whenever we’re in a symmetric monoidal category $C$ with finite colimits, where the tensor product distributes over colimits. To get into your context we should take the tensor product to be cartesian. The group $n!$ acts on $x^n$ , and $x^n/n!$ is the quotient by this action. In this setting we should be able to take $\exp(x+y) = \exp(x) \exp(y)$ , expand out both sides, and get the binomial theorem.

The binomial theorem we get applies to finite sets, which act as coefficients. I guess what’s going on is that $C$ is tensored over $FinSet$ , or something like that. Can we get things like the $q$ -binomial theorem by working with categories tensored over finite-dimensional vector spaces over $\mathbb{F}_q$ ? I don’t know.

This stuff is less exciting than the associahedron-related identity, but if we don’t understand the binomial theorem really well, we don’t stand a chance at fully understanding that fancier identity.

Posted by: John Baez on January 30, 2018 4:03 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

You might be interested in the connections among formal group laws, binomial Scheffer sequences, and compositional inversion of formal power series as discussed in my blog Shadows of Simplicity (https://tcjpn.wordpress.com/2018/01/23/formal-group-laws-and-binomial-sheffer-sequences/).

Posted by: Tom Copeland on March 10, 2018 10:26 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

I’m very curious to see how this theory carries over to other Coxeter permutahedra. They mention in the paper that they are working on this.

Posted by: Simon Burton on January 28, 2018 10:20 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

Hmmm. John writes

the 3d associahedron $\mathbf{c}_4$ has

1 face shaped like ${\mathbf{c}}_4$ ,

6 faces shaped like ${\mathbf{c}}_3 \times \mathbf{c}_1$ and 3 faces shaped like ${\mathbf{c}}_2 \times {\mathbf{c}}_2$ ,

21 faces shaped like ${\mathbf{c}}_2 \times \mathbf{c}_1 \times \mathbf{c}_1$ , and

14 faces shaped like $\mathbf{c}_1 \times \mathbf{c}_1 \times \mathbf{c}_1 \times \mathbf{c}_1$ .

But it seems better to say that

The 3d associahedron $\mathbf{c_4}$ has

1 face shaped like $\overset{∘}{\mathbf{c}}_4$ ,
6 faces shaped like $\overset{∘}{\mathbf{c}}_3 \times \overset{∘}\mathbf{c}_1$ and 3 faces shaped like $\overset{∘}{\mathbf{c}}_2 \times \overset{∘}{\mathbf{c}}_2$ ,
21 faces shaped like $\overset{∘}{\mathbf{c}}_2 \times \overset{∘}\mathbf{c}_1 \times \overset{∘}\mathbf{c}_1$ , and
14 faces shaped like $\overset{∘}\mathbf{c}_1 \times \overset{∘}\mathbf{c}_1 \times\overset{∘}\mathbf{c}_1 \times\overset{∘}\mathbf{c}_1$ .

(a connected component of a space is an open subset, so a point in a discrete space really is its own interior)

So, one possible rephrase of the question: how is a series of negative permutahedra $x - \mathbf{c}_1 x^2 - \mathbf{c}_2 x^3 - \dots$ like an inverse of the series of permutahedron interiors? $x + \overset{∘}\mathbf{c}_1 x^2 + \overset{∘}\mathbf{c}_2 x^3 + \dots$

Posted by: Jesse C. McKeown on January 29, 2018 2:27 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

I think this is a good point, because the open interval $(0,1)$ has Euler–Schanuel characteristic $-1$ ; throw in the points $0$ and $1$ and you get the closed interval $[0,1]$ , with Euler–Schanuel characteristic $-1 + 1 + 1 = 1$ .

The Euler–Schanuel characteristic is an additive function on the algebra of subsets of $\mathbb{R}^n$ generated by convex closed polyhedra, which have Euler–Schanuel characteristic $1$ . It’s also multiplicative under taking cartesian products. So, we can decompose an associahedron in the manner you describe, and compute its Euler–Schanuel characteristic by adding up those of the pieces. I feel this should be part of the answer.

Posted by: John Baez on January 29, 2018 4:58 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

Thank you for writing about this! In case it’s useful to anyone, the slides of my talk at the JMM are on my website:

http://math.sfsu.edu/federico/Talks/JMM2018.pdf

and a video of a similar talk I gave at MSRI in July is here:

https://www.msri.org/people/11876

I am very bad at keeping up with math discussions on the internet but I am often trying to talk to topologists about this. I would love to talk more.

There is much more to this story, but for now, let me share a strange fact, and a related question that has intrigued me for years:

1 - The Strange Fact: Loday found one of many ways of realizing the associahedron as a polytope. With the machinery we build in the paper with Marcelo Aguiar, our theorem about Lagrange inversion is a fairly direct (and unexpected, at least to me) consequence of Loday’s realization; but other realizations of the associahedron give different results! We are exploring this at the moment. But the point is: the polyhedral realization is crucial to our proof.

2 - The Related Question: Combinatorialists know that the associahedron was born in topology, and we love its polyhedral realizations, which are connected to many kinds of beautiful mathematics; but I know of no connections to topology! Might it be useful to topologists that the associahedron is actually (sever)a(l) beautiful polytope(s)?

Posted by: Federico Ardila on January 31, 2018 6:02 AM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

Wow, this is awesome. There is a very didactic PBS video about associahedra in the context of homotopy theory. I think it may be worthy to share it here: https://www.youtube.com/watch?v=N7wNWQ4aTLQ

Posted by: Tadashi on February 1, 2018 1:07 AM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

Gosh! Maths on YouTube has become considerably better produced since the days of the Catsters! :-)

Anyway thanks for that, I didn’t know about that channel. The mathematician in the video is Tai-Danae Bradley, a graduate student at CUNY, who has her own blog MATH3MA. She seems to be taking part in the Adjoint School, so I guess we’ll be hearing from her here at the Café soon…

Posted by: Simon Willerton on February 1, 2018 9:11 AM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

Gosh! Maths on YouTube has become considerably better produced since the days of the Catsters! :-)

Yes, that’s a very well put-together video!

Still, a small part of me misses that regular Catsters panic when you realized you were about to crash into the ten-minute upper limit for YouTube videos (remember that…?)

Posted by: Tom Leinster on February 1, 2018 12:52 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

Federico Ardila’s JMM talk video is here

Posted by: David Roberts on February 10, 2018 3:03 AM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

Is there a pattern with the $c_1$ coefficients? For example, the hexagon term $c_3\times c_1$ gets a $c_1$ factor, but the square $c_2\times c_2$ does not. And the vertices have $c_1$ factors with multiplicity 4.

Posted by: Simon Burton on February 12, 2018 5:47 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

Great question! There must be a great pattern lurking here, since this whole subject is very beautiful. But I don’t see what the pattern is.

Posted by: John Baez on February 12, 2018 5:55 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

I feel silly for not seeing this right away, but the pattern is that the subscript indices of each term here adds to four: $d_4 = -c_4 + 6 c_3 c_1 + 3 c_2^2 - 21 c_2 c_1^2 + 14 c_1^4.$

I only figured this out after looking at Federico’s slides. It seems that each term corresponds to a different way of partitioning a four element set.

Posted by: Simon Burton on February 13, 2018 12:26 AM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

i wonder if this relates to homogeneity

Posted by: lauri love on February 19, 2018 4:01 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

The relations between inversion and permutahedra / permutahedra and associahedra have been known for quite a while. See https://oeis.org/A133437 for the associahedra and https://oeis.org/A133314 and https://oeis.org/A049019 for the permutahedra. Ardila and Aguiar neglect to mention this. See also the MO-Q Guises of the associahedra (https://mathoverflow.net/questions/184803/guises-of-the-stasheff-polytopes-associahedra-for-the-coxeter-a-n-root-system) and the MO-Qs to which it is linked.

Posted by: Tom Copeland on March 10, 2018 8:47 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

See also the MO-Q https://mathoverflow.net/questions/272583/lodays-characterization-and-enumeration-of-faces-of-associahedra-stasheff-poly and https://mathoverflow.net/questions/240319/convex-polytopes-as-products-of-lower-dimensional-polytopes-of-the-same-family and https://math.stackexchange.com/questions/1785526/bijective-mapping-between-face-polytopes-of-permutohedra-and-partitions-of-integ

Posted by: Tom Copeland on March 10, 2018 8:57 PM | Permalink | Reply to this

Re: More Secrets of the Associahedra

$MathML-enabled post (click for more details).$

The Narayana numbers (https://oeis.org/A001263) comprise the h-vectors of the associahedra and its dual, and the refined Narayana vectors (https://oeis.org/A134264) enumerate non-crossing partitions of polygons, which are related to both multiplicative and compositional inversion, and are Appell polynomials in a preferred indeterminate. See also my post An Intriguing Tapestry (https://tcjpn.wordpress.com/2016/11/20/an-intriguing-tapestry-number-triangles-polytopes-grassmannians-and-scattering-amplitudes/), which references Marni Sheppeard, on relations of associahedra to scattering.

Posted by: Tom Copeland on March 10, 2018 11:23 PM | Permalink | Reply to this

The n-Category Café

Skip to the Main Content

January 25, 2018