Given a hereditary property $mathcal H$ of graphs and some $pin[0,1]$, the edit distance function $operatorname{ed}_{mathcal 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 $mathcal H$. For any fixed $pin[0,1]$, $operatorname{ed}_{mathcal H}(p)$ can be computed from an object known as a colored regularity graph (CRG). This paper is concerned with those points $pin[0,1]$ for which infinitely many CRGs are required to compute $operatorname{ed}_{mathcal 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 $operatorname{ed}_{mathcal 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.
تحميل البحث