



















We show that the expected size of the maximum agreement subtree of two $n$-leaf trees, uniformly random among all trees with the shape, is $Θ(\sqrt{n})$. To derive the lower bound, we prove a global structural result on a decomposition of rooted binary trees into subgroups of leaves called blobs. To obtain the upper bound, we generalize a first moment argument for random tree distributions that are exchangeable and not necessarily sampling consistent.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。