On the Largest Common Subtree of Random Leaf-Labeled Binary Trees

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\mathrm{/}8}$ and $n^{1\mathrm{/}2}$. By a construction based on recursive splitting and analyzable by standard “stochastic fragmentation” methods, we improve the lower bound to order $n^{\beta }$ for $\beta =\frac{\sqrt{3}-1}{2}=0.366$. Improving the upper bound remains a challenging problem.