Recent results on the edit distance
of graphs
Meeting Time: Aug. 31, 2010, 2:00-2:50pm
Abstract:
In this talk, we will discuss the edit distance function, a function of a
hereditary property $\mathcal{H}$ and of $p$, which measures the maximum
proportion of edges in a density-$p$ graph that need to be
inserted/deleted in order to transform it into a member of $\mathcal{H}$.
We will describe a method of computing this function and give some results
that have been attained using this method. The edit distance problem has
applications in property testing and evolutionary biology and is closely
related to well-studied Tur\'an-type problems. This is joint work with
Tracy McKay, Iowa State University.