Edit distance and its computation

NEW

Problem: Reconstructed literally: for a nontrivial hereditary class $\mathcal H$ of finite simple graphs, classify inclusion-maximal hereditary superclasses $\mathcal H'\supseteq\mathcal H$ with the same Balogh--Martin asymptotic maximum edit distance $d^*(\mathcal H')=d^*(\mathcal H)$, where $d^*(\mathcal P)=\max_{p\in[0,1]}\operatorname{ed}_{\mathcal P}(p)$.

Result: Under this literal reading, there are no nontrivial maximal superproperties.

Precisely, let $\mathcal U$ be the class of all finite simple graphs. If $\mathcal H=\mathcal U$, the unique maximal superclass is $\mathcal U$. If $\mathcal H\ne\mathcal U$, then no inclusion-maximal hereditary $\mathcal H'\supseteq\mathcal H$ with $d^*(\mathcal H')=d^*(\mathcal H)$ exists.

Proof. First note the key finite-modification lemma. If hereditary properties $\mathcal P,\mathcal Q$ agree on all sufficiently large vertex sets, then $\operatorname{ed}_{\mathcal P}(p)=\operatorname{ed}_{\mathcal Q}(p)$ for every $p$, hence $d^*(\mathcal P)=d^*(\mathcal Q)$.

Now let $\mathcal P\ne\mathcal U$ be hereditary. Choose a finite graph $F\notin\mathcal P$, and define

$$\mathcal Q=\mathcal P\cup\{J:J\text{ is an induced subgraph of }F\}.$$

Then $\mathcal Q$ is hereditary, $\mathcal P\subsetneq\mathcal Q$, and $\mathcal Q$ differs from $\mathcal P$ only on graphs with at most $|V(F)|$ vertices. Therefore $d^*(\mathcal Q)=d^*(\mathcal P)$.

Thus any proper hereditary property can always be strictly enlarged without changing $d^*$. Hence no proper candidate can be maximal.

Finally, if $\mathcal H\ne\mathcal U$, then $d^*(\mathcal H)>0$: choose $F\notin\mathcal H$. Random graphs $G(n,1/2)$ contain $\Omega(n^{|F|})$ induced copies of $F$, while one edge edit destroys only $O(n^{|F|-2})$ such copies, so some graphs are $\Omega(n^2)$-far from $\mathcal H$. Therefore $\mathcal U$, which has $d^*=0$, is not eligible. Hence there is no maximal $\mathcal H'$.

The formulation defect is that $d^*$ is asymptotic and ignores finitely many graph orders. A meaningful repaired question would have to quotient properties by finite-order changes or impose an additional asymptotic/extension-closed notion of maximality.

Citation: Problem from Balogh and Martin, “Edit distance and its computation,” Electron. J. Combin. 15(1) (2008), R20. The resolution above is the elementary finite-modification obstruction.