Article ID Journal Published Year Pages File Type
4667343 Advances in Mathematics 2010 40 Pages PDF
Abstract

We develop combinatorial methods for establishing lower bounds on the rotation distance between binary trees, i.e., equivalently, on the flip distance between triangulations of a polygon. These methods lead to sharp estimates for certain particular pairs of trees. As an application, we prove that, for each n, there exist size n trees at distance , i.e., the diameter of the nth associahedron has at least this value.

Related Topics
Physical Sciences and Engineering Mathematics Mathematics (General)