Uniform semi-Latin squares and their Schur-optimality

摘要

Let n and k be integers, with n>1 and k>0. An (n×n)/k semi-Latin square S is an n×n array, whose entries are k-subsets of an nk-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 nk, 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.