On the locality of the Prüfer code

Abstract

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,T^{\ast }$ is $\Delta (T,T^{\ast })=n-1-|E(T)\cap E(T^{\ast })|$. We randomly mutate the $\mu$th element of the Prüfer string of the tree $T$, changing it to the tree $T^{\ast }$, 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(Δ=\ell | μ)$isontheorderof$ n^{-1/3+o(1)}$foranyinteger$\ell>1,$andthat$P(Δ=1 | μ)=(1-μ/n)^2+o(1).$Thisresultimpliesthattheprobabilityofa‘perfec{t}^{\prime }mutationinthePr\ddot{u}fercode(oneforwhich$Δ(T,T^*)=1$)is$1/3.$

Updated on 4 March 2008, some typos have been corrected