Polynomial-time convergence conjecture for non-increasing edge recoloring

Let KnK_n be the complete graph on nn vertices, and let Φ\Phi be the potential function on colorings of E(Kn)E(K_n) with n1n-1 colors. Consider the process that starts from a random coloring, repeatedly chooses a random edge ee and a random color cc, and recolors ee to cc if this does not increase Φ\Phi. Polynomial-time convergence conjecture. With probability 1on(1)1-o_n(1), this process converges to a one-factorization of KnK_n in time polynomial(n)\operatorname{polynomial}(n). The source presents this as a belief based on simulations and does not establish the claimed high-probability polynomial-time convergence.

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.