Martin's finite CRG conjecture for edit distance functions

Let d4d8d4d8 be a non-trivial hereditary property, and let d4d2(d4d8)d4d2(d4d8) be the set of CRGs avoiding its forbidden graphs. For each pa[0,1]p a[0,1], let gK(p)g_K(p) denote the quadratic minimization function associated with a CRG KK. Martin's finite CRG conjecture. For every d700>0d700>0, there is a finite \subset d4d2\subseteqd4d2(d4d8)d4d2'\subseteqd4d2(d4d8) such that

edH(p)=minKKgK(p),for all p(ε,1ε).\operatorname{ed}_{\mathcal{H}}(p)=\min_{K\in\mathcal{K}'}g_K(p),\qquad\text{for all }p\in(\varepsilon,1-\varepsilon).

This conjecture asks whether the edit distance function is determined by finitely many CRGs uniformly on every compact subinterval of (0,1)(0,1).

Sources & referencesView supporting material

Primary source

Christopher Cox, Ryan R. Martin and Daniel McGinnis, “Accumulation points of the edit distance function”, arXiv:2107.06706 (2022).

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.