\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 Magnus Bordewich, Charles Semple and Mike Steel}
%
%
\medskip
\noindent
%
%
{\bf Identifying $X$-Trees with Few Characters}
%
%
\vskip 5mm
\noindent
%
%
%
%
Previous work has shown the perhaps surprising result that,
for any binary phylogenetic tree ${\cal T}$, there is a set of four
characters that define ${\cal T}$. Here we deal with the general case, where
${\cal T}$ is an arbitrary $X$-tree. We show that if $d$ is the maximum
degree of any vertex in ${\cal T}$, then the minimum number of
characters that identify ${\cal T}$ is $\log_2 d$ (up to a small
multiplicative constant).
\bye