On the rotation distance between binary trees

DOI10.1016/J.AIM.2009.09.016MaRDI QIDQ846983zbMATH OpenOpenAlexFDO

Publication date 16 February 2010

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0901.2557

Binary tree flip rotation distance Thompson's group triangulations

Distance in graphs (05C12) Other groups related to topology or analysis (20F38) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20)

Abstract: We develop combinatorial methods for computing the rotation distance between binary trees, i.e., equivalently, the flip distance between triangulations of a polygon. As an application, we prove that, for each n, there exist size n trees at distance 2n - O(sqrt(n)).

Review text

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\).

Recommendations

Cites work

Cited in

(30)

This page was built for publication: On the rotation distance between binary trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q846983)