On the rotation distance between binary trees (Q846983): Difference between revisions

The tree consisting of a single vertex is denoted by \(\bullet\). If \(T, T'\) are two (finite, binary, rooted, and ordered) trees, \(T^{\,\wedge} T'\) is the tree whose left subtree is \(T\) and right tree is \(T'\). The size of a tree is the number of symbols \(^{\,\wedge}\) in the (unique) expression of the tree in terms of \(\bullet\) and \(^{\,\wedge}\). A tree \(T'\) is obtained from a tree \(T\) by a positive rotation if there exists a inner node \(v\) of \(T\) such that the \(v\)-subtree of \(T\) has the form \(T_1^{\,\wedge} (T_2^{\,\wedge} T_3)\) and \(T'\) is obtained from \(T\) by replacing the \(v\)-subtree with \((T_1^{\,\wedge} T_2)^{\,\wedge} T_3\). In this case, \((T, T')\) is a positive base pair and \((T',T)\) is a negative base pair. If \(T\) and \(T'\) are equal size trees, the minimal number of positive and negative rotations \(\mathrm{dist}(T,T')\) needed to transform \(T\) into \(T'\) is called the rotation distance between \(T\) and \(T'\). For \(n\geq 1\), \(d(n)\) is the maximum of \(\mathrm{dist}(T,T')\) for trees \(T, T'\) of size \(n\). It has been conjectured, that \(d(n)=2n-6\) for all \(n>10\) (cf. [\textit{D. Sleator}, \textit{R.E. Tarjan}, and \textit{W.P. Thurston}, ''Rotation distance, triangulations, and hyperbolic geometry,'' J. Am. Math. Soc. 1, No.\,3, 647--681 (1988; Zbl 0653.51017)], and see [\textit{P. Bose} and \textit{F. Hurtado}, ''Flips in planar graphs,'' Comput. Geom. 42, No.\,1, 60--80 (2009; Zbl 1146.05016)] for a survey). The author proves that \(d(n)\geq 2n-\sqrt{70n}\) for each \(n\), and \(d(n)\geq 2n-2\sqrt{2n} +1\) for \(n=2m^2\).