首页|On the convergence of the mild random walk algorithm to generate random one-factorizations of complete graphs
On the convergence of the mild random walk algorithm to generate random one-factorizations of complete graphs
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Taru Publications
The complete graph K-n, for n even, has a one-factorization (proper edge coloring) with n - 1 colors. In the recent contribution [Dotan M., Linial N. (2017). ArXiv:1707.00477v2], the authors raised a conjecture on the convergence of the mild random walk on the Markov chain whose nodes are the colorings of K-n. The mild random walk consists in moving from a coloring C to a recoloring C' if and only if phi(C') <= phi(C), where phi is the potential function that takes its minimum at one-factorizations. We show the validity of such algorithm with several numerical experiments that demonstrate convergence in all cases (not just asymptotically) with polynomial cost. We prove several results on the mild random walk, we study deeply the properties of local minimum colorings, we give a detailed proof of the convergence of the algorithm for K-4 and K-6, and we raise new conjectures. We also present an alternative to the potential measure phi by consider the Shannon entropy, which has a strong parallelism with phi from the numerical standpoint.
Proper edge coloringOne-factorizationLocal minimum coloringComplete graphMild random walk algorithm
NSTL
Taru Publications
