Finite CRG representation conjecture for edit distance functions
Let be a nontrivial hereditary property. For every , there exists a finite set of colored regular graphs (CRGs) such that
for all .
Finite CRG representation conjecture. For every nontrivial hereditary property and every , the edit distance function is the pointwise minimum of the finitely many functions associated with the CRGs in some finite set , throughout .
This conjecture would show that, away from the endpoints and , 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.
References
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
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.