\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Craig Lennon}
%
%
\medskip
\noindent
%
%
{\bf On the Locality of the Pr\"ufer Code}
%
%
\vskip 5mm
\noindent
%
%
%
%
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$ and $T^*$ is
$\Delta(T,T^*)=n-1-\vert E(T)\cap E(T^*)\vert$.  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\,
\vert \, \mu).$ We find that $P(\Delta=\ell\, \vert \, \mu)$ is on the
order of $ n^{-1/3+o(1)}$ for any integer $\ell>1,$ and that
$P(\Delta=1\, \vert \, \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.$

\bye