论文标题
在最大的随机叶标记二进制树上
On the Largest Common Subtree of Random Leaf-Labeled Binary Trees
论文作者
论文摘要
已知两种独立统一的随机二进制树在$ n $叶子上的最大常见子树（最大协议子树）的大小是在订单之间$ n^{1/8} $和$ n^{1/2} $之间的。通过基于递归分裂和可通过标准“随机片段化”方法分析的结构，我们改善了$β= \ frac {\ sqrt {\ sqrt {3} {3} -1} {2} {2} {2} = 0.366 $的下部键$ n^β$。改善上限仍然是一个具有挑战性的问题。
The size of the largest common subtree (maximum agreement subtree) of two independent uniform random binary trees on $n$ leaves is known to be between orders $n^{1/8}$ and $n^{1/2}$. By a construction based on recursive splitting and analyzable by standard "stochastic fragmentation" methods, we improve the lower bound to order $n^β$ for $β= \frac{\sqrt{3} - 1}{2} = 0.366$. Improving the upper bound remains a challenging problem.
