On the convergence of the mild random walk algorithm to generate random one-factorizations of complete graphs
Ver/ Abrir
Metadatos
Mostrar el registro completo del ítemcomunitat-uji-handle:10234/9
comunitat-uji-handle2:10234/7037
comunitat-uji-handle3:10234/8635
comunitat-uji-handle4:
INVESTIGACIONMetadatos
Título
On the convergence of the mild random walk algorithm to generate random one-factorizations of complete graphsFecha de publicación
2020-05-13Editor
Taylor and Francis; TARU PublicationsISSN
0972-0529; 2169-0065Cita bibliográfica
Julia Calatayud & Marc Jornet (2022) On the convergence of the mild random walk algorithm to generate random one-factorizations of complete graphs, Journal of Discrete Mathematical Sciences and Cryptography, 25:2, 439-454, DOI: 10.1080/09720529.2020.1714884Tipo de documento
info:eu-repo/semantics/articleVersión
info:eu-repo/semantics/acceptedVersionPalabras clave / Materias
Resumen
The complete graph Kn, 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 ... [+]
The complete graph Kn, 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 Kn. The mild random walk consists in moving from a coloring C to a recoloring C′ if and only if ϕ(C′) ≤ ϕ(C), where ϕ 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 K4 and K6, and we raise new conjectures. We also present an alternative to the potential measure ϕ by consider the Shannon entropy, which has a strong parallelism with ϕ from the numerical standpoint. [-]
Publicado en
Journal of Discrete Mathematical Sciences and Cryptography. Volume 25, 2022 - Issue 2Derechos de acceso
info:eu-repo/semantics/openAccess
Aparece en las colecciones
- MAT_Articles [760]