The maximum edit distance from hereditary graph properties (Q933672): Difference between revisions

The edit distance \(E_{\mathcal{P}}(G)\) from a graph \(G\) to a graph property \(\mathcal{P}\) is the minimum number of edge deletions or additions necessary to make \(G\) satisfy \(\mathcal{P}\). \(ed(n,\mathcal{P})\) denotes the maximum such distance over all graphs of order \(n\). In previous work the authors showed that for hereditary \(\mathcal{P}\) (closed under edge deletion), there exists some density \(p=p(\mathcal{P})\in[0,1]\) depending only on \(\mathcal{P}\), such that a random graph \(G(n,p)\) on \(n\) vertices with density \(p\), essentially reaches this maximum, more precisely \(ed(n,\mathcal{P})=E_{\mathcal{P}}(G(n,p))\) with asymptotic probability of 1. In this paper the values \(p(\mathcal{P})\) and \(ed(n,\mathcal{P})\) are determined for several classes of \(\mathcal{P}\), among others the following results. The property \(\mathcal{P}\) is sparse hereditary if the number of labeled graphs on \(n\) vertices satisfying it is \(2^{o(n^2)}\). In this case either all \(G\in \mathcal{P}\) have \(o(n^2)\) edges, and then \(p(\mathcal{P})=1\), or the complements of all \(G\in \mathcal{P}\) have \(o(n^2)\) edges, and then \(p(\mathcal{P})=0\) (in both cases \(ed(n,\mathcal{P})=(1-o(1))\binom{n}{2})\), or otherwise \(p(\mathcal{P})=\frac{1}{2}\) and \(ed(n,\mathcal{P})=(\frac{1}{2}-o(1))\binom{n}{2})\). This applies to the Interval graphs, Permutation graphs or Cographs. For properties closed for complementation one also has \(p(\mathcal{P})=\frac{1}{2}\). For the property \(\mathcal{P}_{r,s}\), consisting of all \((r,s)\)-colorable graphs, i.e. which may be split into \(\leq r\) independent sets and \(\leq s\) cliques, one has \(ed(n,\mathcal{P}_{r,s})=(\frac{1}{(\sqrt{r}+\sqrt{s})^2}-o(1))\binom{n}{2})\). For a graph \(H\) the \(H\)-free property \(\mathcal{P}^*_{H}\) calls for not allowing an induced subgraph isomorphic to \(H\). For claw-free graphs one obtains \(p(\mathcal{P}^*_{K_{1,3}})=\frac{1}{3}\) and \(ed(n,\mathcal{P}^*_{K_{1,3}})=(\frac{1}{3}-o(1))\binom{n}{2})\). For even order square-free graphs \(ed(2n,\mathcal{P}^*_{C_4})=\binom{n}{2}\).