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