The Number of Transversals in a Latin Square
A latin square of order n is an n × 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 bn <
T(n) < cnn!√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.
Various data collected during the writing of this paper can be found at
http://users.m
onash.edu.au/~iwanless/data/transversals/.
Click here to download the whole paper.