Mild random-walk conjecture for one-factorizations

Let KnK_n be the complete graph on nn vertices, and let Gn\mathcal{G}_n be the graph whose vertices are all colorings of E(Kn)E(K_n) with colors 1,,n1{1,\ldots,n-1}, with two colorings adjacent when they differ on exactly one edge. A one-factorization is a proper edge-coloring of KnK_n with n1n-1 colors. In the mild random walk, from a coloring CC one moves uniformly to a neighboring coloring CC' satisfying Ψ(C)Ψ(C)\Psi(C')\leq\Psi(C), where Ψ\Psi counts pairs of incident equally colored edges. Mild random-walk conjecture. The mild random walk on Gn\mathcal{G}_n started from a uniformly random starting point asymptotically almost surely reaches a one-factorization in O(n4)O(n^4) 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

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.