Hong, L. and Miklós, István (2023) A Markov chain on the solution space of edge colorings of bipartite graphs. DISCRETE APPLIED MATHEMATICS, 332. pp. 7-22. ISSN 0166-218X
|
Text
2103.11990v1.pdf Download (225kB) | Preview |
Abstract
In this paper, we exhibit an irreducible Markov chain M on the edge k-colorings of bipartite graphs based on certain properties of the solution space. We show that diameter of this Markov chain grows linearly with the number of edges in the graph and with the number of colors. We also prove a polynomial upper bound on the inverse of acceptance ratio of the Metropolis–Hastings algorithm when the algorithm is applied on M with the uniform distribution of all possible edge k-colorings of G. A special case of our results is the solution space of the possible completions of Latin rectangles. © 2023 Elsevier B.V.
| Item Type: | Article |
|---|---|
| Additional Information: | Department of Mathematics, Massachusetts Institute of Technology, United States Alfréd Rényi Institute of Mathematics, Eötvös Loránd Research Network, Hungary Institute for Computer Science and Control (SZTAKI), Eötvös Loránd Research Network, Hungary Export Date: 18 May 2023 CODEN: DAMAD Correspondence Address: Miklós, I.; Alfréd Rényi Institute of Mathematics, Hungary; email: miklos.istvan@renyi.hu |
| Uncontrolled Keywords: | latin squares; Graph theory; PROPERTY; Markov processes; Edge colorings; K-coloring; Upper Bound; Polynomials; MCMC; Graph-based; Latin square; Edge-colouring; Metropolis-Hastings algorithm; Solution space; Coloring of bipartite graphs; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 30 Mar 2024 20:58 |
| Last Modified: | 30 Mar 2024 20:58 |
| URI: | https://real.mtak.hu/id/eprint/191308 |
Actions (login required)
 |
Edit Item |
