On Maximal Partial Costas Latin Squares

Morgan R. Frank1, Jeffrey H. Dinitz1
1Department of Mathematics and Statistics, University of Vermont 16 Colchester Ave., Burlington, Vermont 05405 U.S.A.

Abstract

A Costas array of order \(n\) is an \(n \times n\) permutation matrix with the property that all of the \(n(n-1)/2\) line segments between pairs of \(1\)’s differ in length or in slope. A Costas latin square of order \(n\) is an \(n \times n\) latin square where for each symbol \(k\), with \(1 \leq k \leq n\), the cells containing \(k\) determine a Costas array. The existence of a Costas latin square of side \(n\) is equivalent to the existence of \(n\) mutually disjoint Costas arrays. In 2012, Dinitz, Östergird, and Stinson enumerated all Costas latin squares of side \(n \leq 27\). In this brief note, a sequel to that paper, we extend this search to sides \(n = 28\) and \(29\). In addition, we determine the sizes of maximal sets of disjoint Costas latin squares of side \(n\) for \(n \leq 29\).