Abstract: A rotation in a binary tree is a local restructuring of the tree, executed by collapsing an internal edge of the tree to a point, thereby obtaining a node with three children, and then re-expanding the node of order three in the alternative way. The rotation distance between a pair of trees with the same number of nodes is the minimum number of rotations needed to convert one tree into another. There has been a great deal of interest in the problems (initially presented by Culik and Wood in 1982 and Sleater, Tarjan and Thurston in 1988): what is the maximum rotation distance between any pair of n-node binary trees? Is there a polynomial time algorithm (in the number of nodes of the trees) to determine the rotation distance between a given pair of trees?
There is a natural link between the rotation distance problem and Thompson’s group F, which has been extensively studied. In this talk, I will discuss a remarkable result by Dehornoy (2010) where he explores this link but ultimately leaves an open problem. Time permitting, I will also discuss a few results which I’m working on at the moment, which might provide a solution to this open problem.