# The Edit Distance Function and Symmetrization

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

### 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,*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.