论文标题
关于平衡树的最大协议子树的猜想
On the maximum agreement subtree conjecture for balanced trees
论文作者
论文摘要
我们对Martin的猜想进行了反例，并认为两个平衡的扎根二进制二进制叶叶树在$ n $叶子上具有最大的协议子树（MAST）的大小至少$ n^{\ frac {\ frac {1} {2}}} $。特别是，我们表明，对于任何$ c> 0 $，在$ n $叶子上存在两个平衡的二进制二进制叶叶树，使得这两棵树的任何桅杆的大小小于$ c n^{\ frac {1} {2} {2}} $。我们还将这种桅杆大小的下限提高到$ n^{\ frac {1} {6}} $。
We give a counterexample to the conjecture of Martin and Thatte that two balanced rooted binary leaf-labelled trees on $n$ leaves have a maximum agreement subtree (MAST) of size at least $n^{\frac{1}{2}}$. In particular, we show that for any $c>0$, there exist two balanced rooted binary leaf-labelled trees on $n$ leaves such that any MAST for these two trees has size less than $c n^{\frac{1}{2}}$. We also improve the lower bound of the size of such a MAST to $n^{\frac{1}{6}}$.
