Martin's finite CRG conjecture for edit distance functions

About 5 years old · traced to

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

ed⁡H(p)=min⁡K∈K′gK(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).

References

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.