On the Distances between Latin Squares and the Smallest Defining Set Size

Abstract

In this note, we show that for each Latin square L of order n≥2 , there exists a Latin square L’≠L of order n such that L and L’ differ in at most 8√n cells. Equivalently, each Latin square of order n contains a Latin trade of size at most 8√n. We also show that the size of the smallest defining set in a Latin square is Ω(n³/²).