Paper Info
Title
Accumulation points of the edit distance function
Abstract
Given a hereditary property 7-t of graphs and some p & nbsp;is an element of [0, 1], the edit distance function ed(H)(p) is (asymptotically) the maximum proportion of "edits " (edge-additions plus edge deletions) necessary to transform any graph of density p into a member of 7-t. For any fixed p is an element of [0, 1], edH(p) can be computed from an object known as a colored regularity graph (CRG). This paper is concerned with those points p is an element of & nbsp; [0, 1] for which infinitely many CRGs are required to compute ed(H )on any open interval containing p; such a p is called an accumulation point. We show that, as expected, p = 0 and p =1 are indeed accumulation points for some hereditary properties; we additionally determine the slope of ed(H) at these two extreme points. Unexpectedly, we construct a hereditary property with an accumulation point at p = 1/4. Finally, we derive a significant structural property about those CRGs which occur at accumulation points. (C)& nbsp;2022 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2022
10.1016/j.disc.2022.112857
DISCRETE MATHEMATICS
Keywords
DocType
Volume
Edit distance, Colored regularity graphs
Journal
345
Issue
ISSN
Citations 
7
0012-365X
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Christopher Cox156.92
Ryan R. Martin23610.12
Daniel McGinnis300.34