The probability of random trees being isomorphic

Christoffer Olsson

Published 2022-05-13Version 1

We show that the probability that two randomly chosen trees are isomorphic decays exponentially for rooted labelled trees as well as Galton--Watson trees with bounded degrees. In the former case a full asymptotic expansion is derived. We also show that, in general, we cannot obtain exponential decay for Galton--Watson trees. Lastly, we prove joint convergence to a multivariate normal distribution for vertices of given degrees in pairs of labelled trees conditioned on being isomorphic.