16
$\begingroup$

( I apologize for only indicating some easy to find references, but new users are not allowed to link more than five). This is very speculative, but:

Question: Is there a reformulation of the Dynamic Optimality Conjecture of Sleator and Tarjan in terms of Thompson's group $F$? (eg. computing lengths of elements wrt some generating set)

Background and reasons to speculate:

  1. In the 80s Sleator and Tarjan invented splay trees, a very celebrated binary search tree which seems to perform better than other search trees. The main question left (and still) open is the conjecture mentioned in the question. For background on this see Sleator and Tarjan, Journal of ACM 1985 or wikipedia: http://en.wikipedia.org/wiki/Splay_tree or the MIT course on data structures by Demaine and Pătrașcu (lecture 3): http://courses.csail.mit.edu/6.897/spring05/lec.html . For background on Thompson's group $F$, the standard reference is http://www.math.binghamton.edu/matt/thompson/cfp.pdf (see also "What is..." Notices AMS 2011)

  2. In a superb failed attempt to solve this problem, Sleator, Tarjan and Thurston (JAMS 1988 http://www.ams.org/mathscinet-getitem?mr=928904) considered the easiest of the operations involved in splaying, rotations between binary trees. This is related with the Associahedron and they indeed computed the diameter of the Associahedron for large values of $n$. (the diameter for all expected values of $n$ was confirmed by Pournin in arxiv 2012)

  3. Dehornoy ( sections 2.2 and 2.3 of http://arxiv.org/abs/0901.2557 ) noticed that the (rotation) distance between two binary trees $T$ and $S$ in the Associahedron equals the length of the element of $F$ represented by $(T,S)$, with respect to a (natural and appropriate) infinite generating set.

  4. The three types of balancing the binary trees appearing in splaying (zig, zig-zig, zig-zag) each correspond (obviously) to an element of $F$... (they are a bit more complicated than just rotations)

  5. More general, all binary search trees use some operations to balance binary trees. The very natural partial action of $F$ on the set of all (rooted ordered finite) binary trees, given by $(T,S)S=T$ (when possible) gives in fact all the ways of balancing a tree. So these connections should not come, of course, as a big surprise. Notice, nevertheless, that for the diameter of Associahedron problem, invoking $F$ didn't provide very strong bounds. This leads to an even more vague question:

Can the geometry of $F$ (which can be seen as a balancing trees machine) say something new about binary search trees, and, especially, can we learn something new about $F$ from Sleator,Tarjan and Thurston and from Pournin (they solved hard problems about $F$ without $F$)?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.