×

A discussion of latin interchanges. (English) Zbl 0867.05010

A partial latin square of order \(n\) is an \(n \times n\) array with entries chosen from a set \(N = \{1,2,...,n\}\) in such a way that each element of \(N\) occurs at most once in each row and column of the array. The set of cells in a partial latin square \(I\) determines the shape of \(I\), and the number of cells is the size of \(I\). A latin square is a partial latin square of size \(n^2\). Two partial latin squares \(I\) and \(I'\) of the same order, size and shape are said to be mutually balanced if the entries in each row (and column) of \(I\) are the same as those in the corresponding row (and column) of \(I'\). They are said to be disjoint if no cell in \(I'\) contains the same entry as the corresponding cell of \(I\). A latin interchange \(I\) is a partial latin square for which there exists another partial latin square \(I'\), of the same order, size and shape, with the property that \(I\) and \(I'\) are disjoint and mutually balanced. The type of a latin interchange is specified by the set of numbers of elements appearing in the non-empty rows and columns. This paper enumerates all latin interchanges of sizes less than 12, thereby verifying and extending the results of D. Keedwell [“Critical sets and critical partial latin squares”, Proc. Third China-USA Int. Conf. on Graph Theory, Combinatorics, Algorithm and Applications, Beijing, June 1993 (to appear)], who enumerated latin interchanges of sizes less than 9. The computer search used by the authors involved first determining all types satisfying a set of necessary conditions for existence of latin interchanges of these types. Each type is modelled by a tripartite graph which is tested for decomposition into triangles by the program autogen developed by P. Adams. If the test is passed, the graph represents a partial latin square. The central idea of this paper is a procedure for modifying this tripartite graph to one which has the property that it can be decomposed into copies of \(K_4\) minus an edge if and only if the original graph represents a latin interchange. The decomposition test is again carried out by autogen. This work has a direct application to the search for critical sets of latin squares.

MSC:

05B15 Orthogonal arrays, Latin squares, Room squares
PDFBibTeX XMLCite