On the locality of the Prüfer code

Details On the locality of the Prüfer code On the locality of the Prüfer code

2008-02-24

arxiv.org/abs/0802.3514v2

Mathematics

Combinatorics

Updated on 4 March 2008, some typos have been corrected

Scientific paper

The Pr\"ufer code is a bijection between trees on the vertex set $[n]$ and strings on the set $[n]$ of length $n-2$ (Pr\"ufer strings of order $n$). In this paper we examine the `locality' properties of the Pr\"ufer code, i.e. the effect of changing an element of the Pr\"ufer string on the structure of the corresponding tree. Our measure for the distance between two trees $T,T^*$ is $\Delta(T,T^*)=n-1-| E(T)\cap E(T^*)|$. We randomly mutate the $\mu$th element of the Pr\"ufer 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\"ufer code (one for which $\Delta(T,T^*)=1$) is $1/3.$

Affiliated with

Also associated with

No associations

Rating

On the locality of the Prüfer code does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the locality of the Prüfer code, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the locality of the Prüfer code will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-427216