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.

  • $\begingroup$ 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. $\endgroup$ – pjs36 Aug 25 '15 at 5:16
  • $\begingroup$ @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. $\endgroup$ – coffeemath Aug 25 '15 at 5:30
  • 1
    $\begingroup$ 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 :) $\endgroup$ – pjs36 Aug 25 '15 at 16:24

See the paper [Joan M. Lucas. The rotation graph of binary trees is Hamiltonian. J. Algorithms, 8(4):503–535, 1987.] which you can access here.

  • $\begingroup$ 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$. $\endgroup$ – coffeemath Aug 25 '15 at 4:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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