On uniformly generating Latin squares

2010/05/02 by Masood Aryapoor, Aryapoor, Masood, E. S. Mahmoodian +1
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Mathematics and Applications #graph theory and CDMA systems #math.CO

paper · pdf · doi:10.48550/arxiv.1005.0121

14 pages; The version to be published in Bull. Inst. Combin. Appl.

openalex publication_date 2010/05/02 · arxiv created 2010/05/18 · arxiv updated 2010/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

By simulating an ergodic Markov chain whose stationary distribution is uniform over the space of nxn Latin squares, Mark T. Jacobson and Peter Matthews [4], have discussed elegant methods by which they generate Latin squares with a uniform distribution (approximately). The central issue is the construction of "moves" that connect the squares. Most of their lengthy paper is to prove that the associated graph is indeed connected. We give a short proof of this fact by using the concepts of Latin bitrades.

Related

• Random Latin squares and Sudoku designs generation
• Quasirandom Latin squares
• Note on random Latin squares and the triangle removal process
• Canonical labelling of Latin squares in average-case polynomial time
• Random sampling of Latin squares via binary contingency tables and probabilistic divide-and-conquer