István Miklós: Fast transformations of Latin squares, half-regular factorizations and edge colorings of bipartite graphs in small steps

Jacobson and Matthew gave perturbations that are necessary and sufficient to transform any n × n Latin square to any another n × n Latin square. In some sense, these perturbations are small: a perturbation changes at most 3 rows. In some sense, they are large: unlimited number of columns might be affected by a single perturbation. These perturbations can be used in a Markov chain Monte Carlo framework to generate random Latin squares. Based on certain properties of the so-emerging Markov chain, these perturbations can be considered as small ones. They also can be considered as fast in the sense that a small number of such perturbations are sufficient to transform any Latin square into any another one.

We show that similar perturbations are possible for half-regular factorizations of complete bipartite graphs and edge colorings of bipartite graphs. That is, we give perturbations that are necessary and sufficient to transform any half-regular factorization of a complete bipartite graph into another half-regular factorization of the same complete bipartite graph. A perturbation affects at most 3 vertices in the first (regular) vertex class and unlimited number of vertices in the second vertex class. These perturbations can be applied in a Markov chain Monte Carlo framework to generate random factorizations, and can be considered as small perturbations. Furthermore, they can be considered as fast because a small number of perturbations are sufficient to transform any factorization into any another one.

Similarly, we give perturbations that are necessary and sufficient to transform any edge k-coloring to another edge k-coloring of a bipartite graph with maximum degree ∆ ≤ k. A perturbation affects at most 3 colors and unlimited number of edges. They can be applied in a Markov chain Monte Carlo framework to generate random edge colorings, and they can be considered as small perturbations. Also, they are fast: a small number of perturbations are sufficient to transform any edge k-colorings into another one. A special case is when the bipartite graph is k-regular, and it is easy to see that this case is equivalent with the completion of Latin rectangles.

Joint work with former BSM students Mark Aksen, Kathleen Zhou and Letong Hong.