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.