Symmetries that Latin squares inherit from 1-factorizations
A 1-factorisation of a graph is a decomposition of the graph into edge
disjoint perfect matchings. There is a well known method, which we
call the K-construction, for building a 1-factorisation of
Kn,n from a 1-factorisation of Kn+1. The
1-factorisation of Kn,n can be written as a latin square of
order n. The K-construction has been used, among other things,
to make perfect 1-factorisations, subsquare-free latin squares and
atomic latin squares.
This paper studies the relationship between the factorisations
involved in the K-construction. In particular, we show how
symmetries (automorphisms) of the starting factorisation are inherited
as symmetries by the end product, either as automorphisms of the
factorisation or as autotopies of the latin square.
Suppose that the K-construction produces a latin square L from a
1-factorisation F of Kn+1. We show that the main class of
L determines the isomorphism class of F (although the converse is
false). We also prove a number of restrictions on the symmetries
(autotopies and paratopies) which L may possess, many of which are
simple consequences of the fact that L must be idempotent and
symmetric (in the usual matrix sense). In some circumstances these
restrictions are tight enough to ensure that L has trivial autotopy
group.
Finally, we give an algorithm for deciding, in time cubic in the order
of the squares, whether a main class of latin squares contains any
square derived from the K-construction. The algorithm also detects
symmetric squares and totally symmetric squares (latin squares which equal
their six conjugates).
Click here to download the whole paper.
Last modified: Fri Sep 26 12:07:00 EST 2003