Premium
On the Edit Distance from K 2 , t ‐Free Graphs
Author(s) -
Martin Ryan R.,
McKay Tracy
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21777
Subject(s) - mathematics , combinatorics , bipartite graph , discrete mathematics , edit distance , vertex (graph theory) , graph , algorithm
The edit distance between two graphs on the same vertex set is defined to be the size of the symmetric difference of their edge sets. The edit distance function of a hereditary property, H , is a function of p , and measures, asymptotically, the furthest graph of edge density p from H under this metric. In this article, we address the hereditary propertyForb ( K 2 , t ) , the property of having no induced copy of the complete bipartite graph with two vertices in one class and t in the other. Employing an assortment of techniques and colored regularity graph constructions, we are able to determine the edit distance function over the entire domain p ∈ [ 0 , 1 ] when t = 3 , 4 and extend the interval over which the edit distance function forForb ( K 2 , t ) is known for all values of t , determining its maximum value for all odd t . We also prove that the function for odd t has a nontrivial interval on which it achieves its maximum. These are the only known principal hereditary properties for which this occurs. In the process of studying this class of functions, we encounter some surprising connections to extremal graph theory problems, such as strongly regular graphs and the problem of Zarankiewicz.