On the number of transversals in Cayley tables of cyclic groups
It is well known that if n is even, the addition table for the
integers modulo n (which we denote by Bn) possesses no
transversals. We show that if n is odd, then the number of
transversals in Bn is at least exponential in n.
Equivalently, for odd n, the number of diagonally cyclic latin squares
of order n, the number of complete mappings or orthomorphisms of the
cyclic group of order n, and the number of placements of n
non-attacking semi-queens on an n × n toroidal chessboard are at
least exponential in n. For all large n we show there is a latin
square of order n with at least (3.246)n transversals.
We diagnose all possible sizes for the intersection of two
transversals in Bn and use this result to complete the
spectrum of possible sizes of homogeneous latin bitrades.
We also briefly explore potential applications of our results in
constructing random mutually orthogonal latin squares.
Click here to download the whole paper.