Removing induced powers of cycles from a graph via fewest edits

Abstract

What is the minimum proportion of edges which must be added to or removed from a graph of density $p$ to eliminate all induced cycles of length $h$? The maximum of this quantity over all graphs of density $p$ is measured by the edit distance function, ${\text{ed}}_{\text{Forb}(C_h)}(p)$, a function which provides a natural metric between graphs and hereditary properties. Martin determined ${\text{ed}}_{\text{Forb}(C_h)}(p)$ for all $p\in [0,1]$ when $h\in \{3,\dots ,9\}$ and determined ${\text{ed}}_{\text{Forb}(C_{10})}(p)$ for $p\in [1/7,1]$. Peck determined ${\text{ed}}_{\text{Forb}(C_h)}(p)$ for all $p\in [0,1]$ for odd cycles, and for $p\in [1/\lceil h/3\rceil ,1]$ for even cycles. In this paper, we fully determine the edit distance function for $C_{10}$ and $C_{12}$. Furthermore, we improve on the result of Peck for even cycles, by determining ${\text{ed}}_{\text{Forb}(C_h)}(p)$ for all $p\in [p_0,1/\lceil h/3\rceil ]$, where $p_0\le c/h^2$ for a constant $c$. More generally, if $C_h^t$ is the $t$-th power of the cycle $C_h$, we determine ${\text{ed}}_{\text{Forb}(C_h^t)}(p)$ for all $p\ge p_0$ in the case when $(t+1)\mid h$, thus improving on earlier work of Berikkyzy, Martin and Peck.

17 pages