The number of transversals in a Latin square

BD McKay, JC McLeod, IM Wanless

Research output: Contribution to journalArticle (Academic Journal)peer-review

56 Citations (Scopus)

Abstract

A Latin Square of order n is an n x n array of n symbols, in which each symbol occurs exactly once in each row and column. A transversal is a set of n entries, one selected from each row and each column of a Latin Square of order n such that no two entries contain the same symbol. Define T(n) to be the maximum number of transversals over all Latin squares of order n. We show that $$b^n \leq T(n) \leq c^n\sqrt{n}\,n!$$ for n â‰¥ 5, where b ≈ 1.719 and c ≈ 0.614. A corollary of this result is an upper bound on the number of placements of n non-attacking queens on an n   n toroidal chess board. Some divisibility properties of the number of transversals in Latin squares based on finite groups are established. We also provide data from a computer enumeration of transversals in all Latin Squares of order at most 9, all groups of order at most 23 and all possible turn-squares of order 14.
Translated title of the contributionThe number of transversals in a Latin square
Original languageEnglish
Pages (from-to)269 - 284
Number of pages16
JournalDesigns, Codes and Cryptography
Volume40 (3)
DOIs
Publication statusPublished - Sept 2006

Bibliographical note

Publisher: Springer

Fingerprint

Dive into the research topics of 'The number of transversals in a Latin square'. Together they form a unique fingerprint.

Cite this