Ryan Martin: On the edit distance in graphs

The edit distance between two graphs on the vertex set $\{1,\ldots,n\}$ is defined to be the size of the symmetric difference of the edge sets, divided by ${n\choose 2}$. The edit distance function of a hereditary property $\mathcal{H}$ is a function of $p\in[0, 1]$ that measures, in the limit, the maximum edit distance between a graph of density $p$ and $\mathcal{H}$. It is also, again in the limit, the edit distance of the Erd\H{o}s-R\’{e}nyi random graph $G(n,p)$ from $\mathcal{H}$. In this talk, we discuss basic results, directions, and connections to other areas of combinatorics.