Mathematics – Combinatorics
Scientific paper
2010-12-03
Mathematics
Combinatorics
15 pages, 10 figures. This article has been withdrawn by the author, as the content now appears in a recently posted combinati
Scientific paper
The edit distance between two graphs on the same vertex set is defined to be size of the symmetric difference of their edge sets. The edit distance function of a hereditary property, $\mathcal{H}$, is a function of $p$ and measures, asymptotically, the furthest graph with edge density $p$ from $\mathcal{H}$ under this metric. The edit distance function has proven to be difficult to compute for many hereditary properties. Some surprising connections to extremal graph theory problems, such as strongly regular graphs and the problem of Zarankiewicz, have been uncovered in attempts to compute various edit distance functions. In this paper, we address the hereditary property $\forb(K_{2,t})$ when $t\geq5$, the property of having no induced copy of the complete bipartite graph with 2 vertices in one class and $t$ in the other. This work continues from a prior paper by the authors. Employing an assortment of techniques and colored regularity graph constructions, we are able to extend the interval over which the edit distance function for this hereditary property is generally known and determine its maximum value for all odd $t$. We also explore several constructions to improve upon known upper bounds for the function.
Martin Ryan
McKay Tracy
No associations
LandOfFree
On the edit distance from $K_{2,t}$-free graphs II: Cases $t\geq 5$ does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the edit distance from $K_{2,t}$-free graphs II: Cases $t\geq 5$, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the edit distance from $K_{2,t}$-free graphs II: Cases $t\geq 5$ will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-515639