论文标题
随机树是同态的概率
The probability of random trees being isomorphic
论文作者
论文摘要
我们研究了两个随机选择的树对不同模型的随机树是同构的可能性。我们表明，对植根的树木以及Galton的概率呈指数衰减 - 具有有界度的Watson树，但对于蓝骨树而言并不是这样，因此在Galton的一般情况下提供了反例 - Watson Trees不受程度限制。我们还针对某些相关参数得出了限制分布：以同构为生的标记树中给定学位的顶点数量，因此表明它们的形状与平常的标记树的形状以及Pólya树的标签和平面代表的数量。结果既取决于概率和分析工具。
We study the fundamental question of how likely it is that two randomly chosen trees are isomorphic to each other for different models of random trees. We show that the probability decays exponentially for rooted labeled trees as well as for Galton--Watson trees with bounded degrees but that this is not true for plane trees, thus providing a counterexample in the general case of Galton--Watson trees without degree restrictions. We also derive limiting distributions for some related parameters: the number of vertices of given degrees in pairs of labeled trees conditioned on being isomorphic, thus showing that they have a different shape than usual labeled trees, as well as the number of labelings and plane representations of Pólya trees. The results rely on both probabilistic and analytic tools.
