\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 J\'ozsef Balogh and Ryan Martin}
%
%
\medskip
\noindent
%
%
{\bf Edit Distance and its Computation}
%
%
\vskip 5mm
\noindent
%
%
%
%
In this paper, we provide a method for determining the asymptotic
value of the maximum edit distance from a given hereditary property.
This method permits the edit distance to be computed without using
Szemer\'edi's Regularity Lemma directly.
Using this new method, we are able to compute the edit distance from
hereditary properties for which it was previously unknown. For some
graphs $H$, the edit distance from ${\rm Forb}(H)$ is computed, where
${\rm Forb}(H)$ is the class of graphs which contain no induced copy of
graph $H$.
Those graphs for which we determine the edit distance asymptotically
are $H=K_a+E_b$, an $a$-clique with $b$ isolated vertices, and
$H=K_{3,3}$, a complete bipartite graph. We also provide a graph, the
first such construction, for which the edit distance cannot be
determined just by considering partitions of the vertex set into
cliques and cocliques.
In the process, we develop weighted generalizations of Tur\'an's
theorem, which may be of independent interest.
\bye