Accumulation points of the edit distance function

Abstract

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

arXiv comment22 pages