IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

On the edit distance function of random graphs

  • Sept. 4, 2020
  • 2:30 p.m.


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ős-Ré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$,

$${\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\}.$$

Moreover, this holds for $p\in [1/3,2/3]$ for any $p _ 0\in (0,1)$.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster