Orthogonality and extendability of latin squares and related structures

摘要

Two of the most important topics in the study of latin squares are questions of orthogonality and extendability. A latin square of order n is an nxn array consisting of n distinct symbols such that each of n symbols occurs precisely once in each row and column. Two latin squares are said to be orthogonal if no two cells contain the same ordered pair of symbols when the squares are superimposed. There are many generalizations of latin squares, and in these generalizations there is a natural notion of orthogonality. In particular, we can view a latin square as a coloring of a graph. We say that two colorings of a graph are orthogonal if, whenever two vertices share a color in one coloring, then they have a different color in the other coloring.;It is well known that there cannot be more than n -- 1 pairwise orthogonal latin squares of order n. Given a graph, G, we seek a bound on the maximum size of a set of pairwise orthogonal colorings of G. We derive several upper bounds based on parameters of the graph such as the number of vertices and edges, the maximum degree of a vertex, or the existence of large cliques. As a consequence we establish upper bounds on the maximum cardinality of a set of pairwise orthogonal colorings for several latin structures including latin rectangles, row latin squares, single diagonal latin squares, and double diagonal latin squares. We show that these bounds are the best possible.;Questions about the extendability of latin squares are related to obtaining a latin square from a partially filled latin square. A partial latin square of order n is an nx n array consisting of n symbols such that each of n symbols occurs at most once in each row and column. It is an NP-complete problem to determine whether a partial latin square can be completed to a latin square of the same order. In 1974 Alan Cruse derived necessary and sufficient conditions to extend a partial latin rectangle to a latin square. Here we provide an alternate proof of Cruse's Theorem. Then we use the tools of this new and different proof to prove an analogous theorem for frequency squares. A frequency square of type F( n;lambda1,...,lambda k) is an nxn array filled with k symbols if the symbol i occurs in each row and column precisely lambda i times.;A partial transversal of size r in a latin square is a set of r cells representing distinct rows, columns, and symbols. We show that the questions of orthogonality and extendability overlap with the question of the existence of a (partial) transversal of latin squares. The problem of finding a (partial) transversal in a latin square can be recast in terms of extending portions of a latin square or in terms of the parameters of the graph obtained from a coloring that defines the latin square. We extend the well known conjectures of Bualdi and Ryser on the existence of (partial) transversals and propose a few tools for tackling these conjectures.