9
$\begingroup$

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.

  • 0
    @Theo Ye$s$, 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.2011-08-15

2 Answers 2

4

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

  • 0
    +1 for finding Emanuele! Nice guy; he was in the class one or two years below mine at ETH Zurich.2011-08-15
2

Check http://oeis.org/A126216 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.

  • 0
    Not sure, it answers my question. But it's interesting anyway, thank you.2011-09-30