PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Becky Halpenny.

Title:"Orthogonality and Extendability of Latin Squares and Related Structures"
Seminar:Ph.D. Thesis Defense
Speaker:Serge Ballif, Adviser: Gary Mullen
Abstract Link:http://
Abstract:
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 $n \times n$ array consisting of $n$ symbols such that each of $n$ distinct 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 $n\times 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 as to 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 proof to prove an analogous theorem for frequency squares. A frequency square of type $F(n;\lambda_1,\ldots,\lambda_k)$ is an $n\times n$ array filled with $k$ symbols if the symbol $i$ occurs in each row and column precisely $\lambda_i$ times.

Room Reservation Information

Room Number:203 EE West
Date:02 / 14 / 2012
Time:12:30pm - 02:30pm