A Markov chain on the solution space of edge colorings of bipartite graphs (Q2696608)

The authors construct a Markov chain whose states are all the \(k\)-edge-colourings of any given bipartite graph \(G\), and such that the distribution converges to the uniform distribution. The Markov chain is constructed using a Markov Chain Monte Carlo approach, using the well-known Metropolis-Hastings algorithm. In this application, the Markov chain can be briefly described as follows. Starting from any \(k\)-edge-colouring, perform a random ``local change'' in this colouring (i.e. modifying a small proportion of the coloured edges). With certain ``acceptance probability'' (depending on the local change) the change is accepted and the colouring is updated; with the complementary probability the colouring is unchanged. The authors implement this idea using a particular set of ``local changes'', and are able to show that the obtained Markov chain has several desirable properties. This Markov chain has diameter at most \(2km\) if \(G\) has \(m\) edges (i.e. it is possibly to obtain any prescribed \(k\)-edge-colouring of G, starting from any other prescribed \(k\)-edge-colouring of G, using at most \(2km\) local changes). It also has ``acceptance probability'' whose inverse is bounded from above by a polinomial on the number of vertices of \(G\). This generalises previous results by Jacobson and Matthew and of Aksen et al., who constructuted similar Markov chains for (edge-colourings of) specific bipartite graphs. The authors also study in more detail the specific case where \(k\)-edge-colourings of \(k\)-regular bipartite graphs are considered. In this case, the bounds obtained previous analysis can be improved. An application of this last part is given to the problem of sampling a random completion of certain incomplete Latin squares.