Finite CRG representation conjecture for edit distance functions

Let H\mathcal{H} be a nontrivial hereditary property. For every ε>0\varepsilon>0, there exists a finite set of colored regular graphs (CRGs) K=K(ε,H)\mathcal{K}'=\mathcal{K}'(\varepsilon,\mathcal{H}) such that

edH(p)=min{gK(p):KK}\operatorname{ed}_{\mathcal{H}}(p)=\min\left\{g_K(p):K\in\mathcal{K}'\right\}

for all p(ε,1ε)p\in(\varepsilon,1-\varepsilon).

Finite CRG representation conjecture. For every nontrivial hereditary property H\mathcal{H} and every ε>0\varepsilon>0, the edit distance function edH(p)\operatorname{ed}_{\mathcal{H}}(p) is the pointwise minimum of the finitely many functions gK(p)g_K(p) associated with the CRGs in some finite set K(ε,H)\mathcal{K}'(\varepsilon,\mathcal{H}), throughout p(ε,1ε)p\in(\varepsilon,1-\varepsilon).

This conjecture would show that, away from the endpoints 00 and 11, edit distance functions of hereditary properties can always be determined by finitely many colored regular graphs. The supplied text does not state whether the conjecture is known or open.

Sources & referencesView supporting material

Primary source

Ryan R. Martin and Alexander W. N. Riasanovsky, “On the edit distance function of the random graph”, arXiv:2007.08409 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.