Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Recall that faces of associahedra are indexed by planar trees aka configurations of non-interesecting diagonals in polygons. And incidence corresponds to contracting edges / removing diagonals.

Vertices of associahedra can also be indexed by Dyck paths. What is the corresponding interpretation for all faces? How can incidence be described in these terms?

Some thoughts. Actually, I'm quite sure that faces are indexed by (small) Schröder paths.

Heuristic explanation: edges correspond to “elementary switches” and the most natural transformation one can do to a Dyck path is to switch RU<->UR (R standing for a step right, U — for a step up, naturally); let's mark the place of switches by diagonal steps — now we get Schröder paths (small Schröder paths, actually: diagonal steps can't lie on the main diagonal — or the “UR end” of the switch would intersect the main diagonal). Note that this heuristic also describes the incidence relation — but this description is clearly wrong: it predicts that the vertex $R^nU^n$ lies only on one edge (namely, on the $U^{n-1}DR^{n-1}$).

Recall that bijection between non-associative products and Dyck paths is given by Reverse Polish notation — so swtiches should correspond not to corners but just to vertical steps (and the symmetry between horizontal and vertical steps breaks). Anyway, now it's not hard to write down some examples. For 2-associahedron aka pentagon, say: the cyclic order of vertices coming from $$((ab)c)d\to (a(bc))d\to a((bc)d)\to a(b(cd))\to (ab)(cd)\to$$ is $$RURURU\to RRUURU\to RRURUU\to RRRUUU\stackrel{(!)}\to RURRUU\to $$ (note the step (!) not agreeing with naive heuristic).

Dyck paths as vertices of 2-associahedron

But I have no idea how to describe the incidence relation in general case.

share|cite|improve this question
I don't know if this helps, but browsing a little revealed these nice notes by Fomin and Reading, which describe the $(n-3)$-dimensional associahedron in terms of triangulations of the $n$-gon. Very nice. This doesn't quite yield a description via Dyck paths, but on the other hand why insist? After all, there are many things enumerated by the Catalan numbers and maybe Dyck paths are not exactly the handiest implementation? – t.b. Aug 15 '11 at 9:31
@Theo Yes, this description (which is, up to obvious bijection, coincides with the original definition, I believe) is definitely very clear. The motivation for the question (well, beyond natural curiosity) is that there is some embedding of n-associahedron into Euclidean space that is easier to describe in terms of paths. – Grigory M Aug 15 '11 at 9:37
up vote 4 down vote accepted

(Omniscient Google taught me that) a bijection between bracketings and Schröder paths is described clearly in E. Delucchi's handouts.

Description of the incidence relation definitely can be extracted from this bijection but I failed to do it so far.

Update (05.2013). The incidence relation («flips between Dyck paths») is described in M. Gorsky's preprint (see section 2.2).

share|cite|improve this answer
+1 for finding Emanuele! Nice guy; he was in the class one or two years below mine at ETH Zurich. – t.b. Aug 15 '11 at 10:00

Check and A133437 for an answer. Follow A033282 to A133437 and A126216. Also, there is a connection between the h-polynomials of the associahedra and Dyck paths. Follow A001263 to A134264 and then to A125181.

share|cite|improve this answer
Not sure, it answers my question. But it's interesting anyway, thank you. – Grigory M Sep 30 '11 at 13:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.