# Recent results on the edit distance of graphs

• Ryan Martin (Iowa State University)
• Thursday 14 October 2010, 14:30-15:30
• MR12.

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.

This talk is part of the Combinatorics Seminar series.