Finite CRG representation conjecture for edit distance functions
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.