### The Edit Distance Function and Symmetrization

#### Abstract

The edit distance between two graphs on the same labeled vertex set is the size of the symmetric difference of the edge sets. The distance between a graph,

This paper utilizes a method due to Sidorenko [

*G*, and a hereditary property, ℋ, is the minimum of the distance between*G*and each*G'*∈ℋ. The edit distance function of ℋ is a function of*p*∈[0,1] and is the limit of the maximum normalized distance between a graph of density*p*and ℋ.This paper utilizes a method due to Sidorenko [

*Combinatorica***13**(1), pp. 109-120], called "symmetrization", for computing the edit distance function of various hereditary properties. For any graph*H*, Forb(*H*) denotes the property of not having an induced copy of*H*. This paper gives some results regarding estimation of the function for an arbitrary hereditary property. This paper also gives the edit distance function for Forb(*H*), where*H*is a cycle on 9 or fewer vertices.#### Keywords

edit distance, hereditary properties, symmetrization, cycles, colored regularity graphs, quadratic programming