{
  "id": "1007.1897",
  "version": "v5",
  "published": "2010-07-12T13:21:55.000Z",
  "updated": "2012-02-12T16:41:09.000Z",
  "title": "The edit distance function and symmetrization",
  "authors": [
    "Ryan Martin"
  ],
  "comment": "Revised 2/12/12",
  "journal": "Electron. J. Combin. 20(3) (2013), Research Paper 26, 25pp",
  "categories": [
    "math.CO"
  ],
  "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, ${\\cal H}$, is the minimum of the distance between $G$ and each $G'\\in{\\cal H}$. The edit distance function of ${\\cal H}$ is a function of $p\\in[0,1]$ and is the limit of the maximum normalized distance between a graph of density $p$ and ${\\cal H}$. This paper develops a method, called localization, for computing the edit distance function of various hereditary properties. For any graph $H$, ${\\rm 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 ${\\rm Forb}(H)$, where $H$ is a cycle on 9 or fewer vertices.",
  "revisions": [
    {
      "version": "v5",
      "updated": "2012-02-12T16:41:09.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C80"
    ],
    "keywords": [
      "edit distance function",
      "symmetrization",
      "arbitrary hereditary property",
      "maximum normalized distance",
      "labeled vertex set"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1007.1897M"
    }
  }
}