×

Edit distance and its computation. (English) Zbl 1159.05030

Summary: We provide a method for determining the asymptotic value of the maximum edit distance from a given hereditary property. This method permits the edit distance to be computed without using Szemerédi’s Regularity Lemma directly.
Using this new method, we are able to compute the edit distance from hereditary properties for which it was previously unknown. For some graphs \(H\), the edit distance from \(\text{Forb}(H)\) is computed, where \(\text{Forb}(H)\) is the class of graphs which contain no induced copy of graph \(H\).
Those graphs for which we determine the edit distance asymptotically are \(H=K_a+E_b\), an \(a\)-clique with \(b\) isolated vertices, and \(H=K_{3,3}\), a complete bipartite graph. We also provide a graph, the first such construction, for which the edit distance cannot be determined just by considering partitions of the vertex set into cliques and cocliques.
In the process, we develop weighted generalizations of Turán’s theorem, which may be of independent interest.

MSC:

05C35 Extremal problems in graph theory
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: arXiv EuDML EMIS