THE INTERSECTIONS OF COMMUTATIVE LATIN SQUARES

Abstract

A latin square of order n is an nxn array such that each of the integers 1,2,...,n (or any set of n distinct symbols) occurs exactly once in each row and each column. A latin square L = [l(i),j] is said to be commutative provided that l(i),j = l(j),i for all i and j. Two latin squares, L = [l(i),j] and M = [m(i),j], are said to have intersection k if there are exactly k cells (i,j) such that l(i),j = m(i),j. Let I[n] = {0,1,2,...,n2-9,n2-8,n2-6,n2}, H[n] = I[n] union {n2-7,n2-4}, and J[n] be the set of all integers k such that there exists a pair of commutative latin squares of order n which have intersection k. In this paper, we prove that J[n] = I[n] for each odd n greater-than-or-equal-to 7, J[n] = H[n] for each even n greater-than-or-equal-to 6, and give a list of J[n] for n less-than-or-equal-to 5. This totally solves the intersection problem of two commutative latin squares.