Efficient, local and symmetric Markov chains that generate one-factorizations (Q2216928)

The paper under review is concerned with 1-factorisations of complete graphs on \(n\) vertices where \(n\) is even, i.e. decompositions of their edge set into \(n-1\) perfect matchings (equivalently, proper edge-colourings of \(K_{n}\) with the minimum number \(n-1\) of colours). While the existence of 1-factorizations of complete graphs on an even number of vertices has been known for a long time, not much is known about their structure. The authors introduce Markov chains which are random walks on the graph whose vertex set \(\mathcal{V}_{n}\) is the set of all \((n-1)\)-edge colourings of \(K_{n}\), with the aid of a potential function \(\Psi\) which vanishes if and only if the colouring is a one-factorisation and measures how far the current edge-colouring is from being a 1-factorization. While perhaps the natural such graph to consider of this type would be the one with edges between two colourings if and only if they differ on exactly one edge, this approach can get stuck at a local minimum which is not a 1-factorization. As such the authors consider a graph \(\mathcal{G}_{n}\) with the same vertex set but which contains certain additional directed edges related to the structure of local minima. \par The strict random walk is then one which, when it is currently at state \(C\), chooses uniformly at random a neighbour \(C^{\prime}\) if and only if \(\Psi (C^{\prime})>\Psi (C)\). The main result in the paper under review is that there is a strict random walk that, from every starting point, converges to a one-factorization in O\((n^{3})\) steps. \(\mathcal{G}_{n}\) has the desirable properties of symmetry (invariance under changing the names of the \(n\) vertices and of the \(n-1\) colours), locality (that the new state \(C^{\prime}\) and old state \(C\) differ on at most O\((n)\) edges) and efficiency (in that a random step in \(\mathcal{G}_{n}\) can be sampled in time polynomial in \(n\)). \par The authors also consider the so-called mild random walk, which goes from \(C\) to \(C^{\prime}\) if and only if \(\Psi(C^{\prime})\geq \Psi(C)\) (greater than or equal to rather than the strict inequality in the definition of the strict random walk). They conjecture that, from a uniformly random starting point, it will, with probability tending to 1 as \(n\rightarrow\infty\), reach a one-factorization in time \(\overline{\mathrm{O}}(n^{4})\) where are usual \(\overline{\mathrm{O}}\) can conceal logarithmic factors. An important limitation of the methods is that there is no reason to believe that either the strict or the mild walk reaches a uniformly distributed 1-factorization. and the authors pose a problem on this in relation to another variant, the so-called weak walk.