{
  "id": "2007.08409",
  "version": "v1",
  "published": "2020-07-16T15:36:56.000Z",
  "updated": "2020-07-16T15:36:56.000Z",
  "title": "On the edit distance function of the random graph",
  "authors": [
    "Ryan R. Martin",
    "Alexander W. N. Riasanovsky"
  ],
  "comment": "33 pages, 3 figures",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "Given a hereditary property of graphs $\\mathcal{H}$ and a $p\\in [0,1]$, the edit distance function ${\\rm ed}_{\\mathcal{H}}(p)$ is asymptotically the maximum proportion of edge-additions plus edge-deletions applied to a graph of edge density $p$ sufficient to ensure that the resulting graph satisfies $\\mathcal{H}$. The edit distance function is directly related to other well-studied quantities such as the speed function for $\\mathcal{H}$ and the $\\mathcal{H}$-chromatic number of a random graph. Let $\\mathcal{H}$ be the property of forbidding an Erd\\H{o}s-R\\'{e}nyi random graph $F\\sim \\mathbb{G}(n_0,p_0)$, and let $\\varphi$ represent the golden ratio. In this paper, we show that if $p_0\\in [1-1/\\varphi,1/\\varphi]$, then a.a.s. as $n_0\\to\\infty$, \\begin{align*} {\\rm ed}_{\\mathcal{H}}(p) = (1+o(1))\\,\\frac{2\\log n_0}{n_0} \\cdot\\min\\left\\{ \\frac{p}{-\\log(1-p_0)}, \\frac{1-p}{-\\log p_0} \\right\\}. \\end{align*} Moreover, this holds for $p\\in [1/3,2/3]$ for any $p_0\\in (0,1)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-07-16T15:36:56.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C80"
    ],
    "keywords": [
      "edit distance function",
      "random graph",
      "edge-additions plus edge-deletions",
      "golden ratio",
      "hereditary property"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 33,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}