TY - JOUR

T1 - On the number of transversals in Cayley tables of cyclic groups

AU - Cavenagh, Nicholas

AU - Wanless, Ian Murray

PY - 2010

Y1 - 2010

N2 - 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, the number of magic juggling sequences of period 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 that 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.

AB - 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, the number of magic juggling sequences of period 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 that 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.

UR - http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYW-4XBF8R0-2&_user=542840&_coverDate=01%2F28%2F2010&_rdoc=1&_fmt=high&_orig=search&_sort=d

M3 - Article

VL - 158

SP - 136

EP - 146

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -