tailieunhanh - Báo cáo toán học: "Edit distance and its computation"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Edit distance and its computation. | Edit distance and its computation Jozsef Balogh Ryan Martiny Submitted Sep 26 2007 Accepted Jan 17 2008 Published Jan 28 2008 Mathematics Subject Classification 05C35 05C80 Abstract In this paper 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 Szemeredi 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 Forb H is computed where 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 Ka Eb an a-clique with b isolated vertices and H K33 a complete bipartite graph. We also provide a graph the Erst 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 Turan s theorem which may be of independent interest. 1 Introduction Throughout this paper we use standard terminology in the theory of graphs. See for example 6 . A subgraph devoid of edges usually called an independent set is referred to in this paper as a coclique so that it parallels the notion of a clique. Background The edit distance of graphs was defined in 4 as follows Department of Mathematics University of Illinois at Urbana-Champaign Urbana IL 61801 jobal@. This author s research supported in part by NSF grant DMS-0600303 UIUC Campus Research Board 07048 and by OTKA grants T034475 and T049398. yDepartment of Mathematics Iowa State University Ames IA 50011 rymartin@. This author s research supported in part by NSA grant H98230-05-1-0257. THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2007 R20 1 Definition 1 Let P denote a class of graphs. If G is a fixed graph then the edit .