# Hamiltonian cycles in associahedron graphs

Let two distinct fully parenthesized products of $n$ symbols be called adjacent provided one of them may be obtained from the other by a single application of the associative law. Such graphs may be viewed as "associahedrons", though my question doesn't involve the graph theory approach so much, and in my case I assume for fixed $n$ that the graph contains as vertices all the parenthesized products. For example, for $n=4$ there are five vertices, each adjacent to $2$ others, and so essentially two possible Hamiltonian cycles. I found that in the case of $n=5$ it was possible to find a Hamiltonian cycle going through all $14$ vertices. (Here I think there are more than one such cycle...)

My question is what happens for larger $n.$ I tried $n=6$ and got close, proceeding by using cycles from previous cases and "sewing them up" into a complete cycle. However I got lost in the details. So I'm curious about the $n=6$ case, and in general for higher $n$ is there a known cutoff beyond which it is known no Hamiltonian cycle exists.

Associahedron reference at Wiki is here

Here's the list I found for the $n=5$ case: $$(((12)3)4)5 \\ ((1(23))4)5 \\ (1((23)4))5 \\ (1(2(34)))5 \\ ((12)(34))5 \\ (12)((34)5) \\ (12)(3(45)) \\ 1(2(3(45))) \\ 1(2((34)5)) \\ 1((2(34))5) \\ 1(((23)4)5) \\ 1((23)(45)) \\ (1(23))(45) \\ ((12)3)(45)$$

Each is adjacent to the one below in the sense of one use of associative law, including the final one back to the first, to complete the cycle.

• I like this question a lot. While I see you've probably got the literature answering your question, I'll work on a nice formulaic cycle. – pjs36 Aug 25 '15 at 5:16
• @pjs36 If there really is a "formulaic" cycle (even for $n=6$) I'd definitely upvote an answer about that. The hard thing for me is how to notate the various parenthesizations nicely, along with a test for use of the associative law in such a notation. – coffeemath Aug 25 '15 at 5:30
• The notation is a pain and if I use any, it'll probably be related to partitions. My background here is graphical, via graph associahedra. I'm not certain I'll find anything, but I'll keep spending time with it :) – pjs36 Aug 25 '15 at 16:24

• Thanks for this reference. I had a look and it seems it will take some time (for me) to digest it, but it seems to say in my sense that there's a Hamiltonian cycle for any choice $n$. – coffeemath Aug 25 '15 at 4:39