Path-type description for (faces of) associahedra?

459 Views Asked by At

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.

2

There are 2 best solutions below

1
On BEST ANSWER

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

1
On

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.