On the Edit Distance in Graphs

Thursday, December 4, 2014 - 2:00pm - 3:00pm
Lind 305
Ryan Martin (Iowa State University)
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 survey the topic and describe symmetrization, a method that can be used in computing this function and we will give some results that have been attained using it. The edit distance problem has applications in property testing and evolutionary biology and is closely related to well-studied Tur\'an-type problems. Some of the more intriguing results will show a close relationship between the problem of Zarankiewicz as well as strongly regular graphs. This is a survey including joint work with Maria Axenovich (Karlsruhe), J\'ozsef Balogh (Illinois), Andr\'e K\'ezdy (Louisville), Tracy McKay (Dickinson College) and Chelsea Peck (ISU).