Uniform Semi‐Latin Squares and Their Schur‐Optimality

Let n and k be integers, with n > 1 and k > 0 . An ( n × n ) / ksemi‐Latin square S is an n × n array, whose entries are k ‐subsets of an n k ‐set, the set of symbols of S , such that each symbol of S is in exactly one entry in each row and exactly one entry in each column of S . Semi‐Latin squares form an interesting class of combinatorial objects which are useful in the design of comparative experiments. We say that an ( n × n ) / k semi‐Latin square S is uniform if there is a constant μ such that any two entries of S , not in the same row or column, intersect in exactly μ symbols (in which case k = μ ( n − 1 ) ). We prove that a uniform ( n × n ) / k semi‐Latin square is Schur‐optimal in the class of ( n × n ) / k semi‐Latin squares, and so is optimal (for use as an experimental design) with respect to a very wide range of statistical optimality criteria. We give a simple construction to make an ( n × n ) / k semi‐Latin square S from a transitive permutation group G of degree n and order n k , and show how certain properties of S can be determined from permutation group properties of G . If G is 2‐transitive then S is uniform, and this provides us with Schur‐optimal semi‐Latin squares for many values of n and k for which optimal ( n × n ) / k semi‐Latin squares were previously unknown for any optimality criterion. The existence of a uniform ( n × n ) / ( ( n − 1 ) μ ) semi‐Latin square for all integers μ > 0 is shown to be equivalent to the existence of n − 1 mutually orthogonal Latin squares (MOLS) of order n . Although there are not even two MOLS of order 6, we construct uniform, and hence Schur‐optimal, ( 6 × 6 ) / ( 5 μ ) semi‐Latin squares for all integers μ > 1 . & 2012 Wiley Periodicals, Inc. J. Combin. Designs 00: 1–13, 2012