Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The Tamari lattice is a poset whose objects are ways of bracketing a sequence into pairs - for example (a(bc))d - with the covering relation being rightward application of the associative law, ie $((ab)c) \lessdot (a(bc))$.

(Equivalently, and what I'm actually interested in, the objects can be thought of as binary trees, and the covering relation as rightward rotation.)

Given two elements x,y in the lattice, is there a more efficient algorithm for finding out whether $x < y$ than just generating the up-set of x by iteration of the covering relation and then checking whether y is in it? For example, if you think of that as a graph search, is there a way to see early that a branch of the search can't possibly work, and prune it?

(I'm aware that there may be algorithms involving switching to the poset of permutations with the weak order, but if possible I'd prefer a more direct algorithm.)

share|improve this question

1 Answer 1

I think it is possible. Consider two expressions

(...xabc)(y..)
(...)(xabcy..)

On every level you can move the splitting point to the left only, so at every given node you need to check if the number of leafs in the left subtree is greater or equal the number of leafs in the right subtree. Moreover, there is no right subtree you could split (if something went to right subtree, it stays there forever), so when checking if you can move the splitting point you need to check that all the right subtrees you are moving are taken as a whole. If that condition is satisfied it is easy to find proper rotations-- just rotate all the nodes from bottom (the place where you want to make the split) all the way up to the level you have started at.

((((A    x) a) b) c) (y......)
((( A   (x  a))b) c) (y......)
((  A  ((x  a )b))c) (y......)
(   A (((x  a )b )c))(y......)
    A((((x  a )b )c))(y......))

Of course the $A, x, a, b, c, y$ may be arbitrary subtrees--the important thing is: split may happen only before left-most vertex of the right-subtree (left-most vertex of subtree $x$ in the example). After this process you will have the correct split at given level, and then just do both branches recursively. If you succeed, it you have found your transition, if not, you will find the reason why it is impossible.

To be exactly sure it works as intended, please prove it before you use it (it is possible that I missed something).

Have fun!

share|improve this answer

Your Answer

 
discard

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.