Latin squares whose transversals intersect in unusual ways
A latin square of order n is an n×n array in which each of n
symbols occurs exactly once in each row and column. A transversal in
such a square is a selection of n entries that includes one
representative of each row and column, and one of each symbol. For
all even orders n≥28 we construct a latin square of order n in
which every pair of transversals share at least one entry. We
conjecture that in our squares there is no single entry that is common
to all transversals. We prove this conjecture for n≤10000 by
finding transversals using an algorithm that is likely to be of
independent interest.
We say that a transversal is dominant if it intersects every other
transversal of the same latin square. We show that there exist latin
squares of order n that have a dominant transversal for n in {5,7} and
also for all n≥8 such that n≢3 mod 4.
Various data collected during the writing of this paper can be found at
http://users.monash.edu.au/~iwanless/data/transversals/.