On the locality of the Prüfer code (Q1010914)

Summary: The Prüfer code is a bijection between trees on the vertex set \([n]\) and strings on the set \([n]\) of length \(n-2\) (Prüfer strings of order \(n\)). In this paper we examine the `locality' properties of the Prüfer code, i.e. the effect of changing an element of the Prüfer string on the structure of the corresponding tree. Our measure for the distance between two trees \(T\) and \(T^*\) is \(\Delta(T,T^*)=n-1-| E(T)\cap E(T^*)|\). We randomly mutate the \(\mu\)th element of the Prüfer string of the tree \(T\), changing it to the tree \(T^*\), and we asymptotically estimate the probability that this results in a change of \(\ell\) edges, i.e. \(P(\Delta=\ell\, | \, \mu)\). We find that \(P(\Delta=\ell\, | \, \mu)\) is on the order of \( n^{-1/3+o(1)}\) for any integer \(\ell>1,\) and that \(P(\Delta=1\, | \, \mu) = (1-\mu/n)^2+o(1)\). This result implies that the probability of a `perfect' mutation in the Prüfer code (one for which \(\Delta(T,T^*)=1\)) is \(1/3.\)