Mild random-walk conjecture for one-factorizations
Mild random-walk conjecture for one-factorizations
Let be the complete graph on vertices, and let be the graph whose vertices are all colorings of with colors , with two colorings adjacent when they differ on exactly one edge. A one-factorization is a proper edge-coloring of with colors. In the mild random walk, from a coloring one moves uniformly to a neighboring coloring satisfying , where counts pairs of incident equally colored edges. Mild random-walk conjecture. The mild random walk on started from a uniformly random starting point asymptotically almost surely reaches a one-factorization in steps. The conjecture is presented as supported by numerical evidence; no resolution is given in the source.
Sources & referencesView supporting material
Primary source
Maya Dotan and Nati Linial, “Efficient Generation of One-Factorizations through Hill Climbing”, arXiv:1707.00477 (2017).
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.