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\ge 2$, there exists a Latin square $L^{\prime }\ne L$ of order $n$ such that $L$ and $L^{\prime }$ differ in at most $8\sqrt{n}$ cells. Equivalently, each Latin square of order $n$ contains a Latin trade of size at most $8\sqrt{n}$. We also show that the size of the smallest defining set in a Latin square is $\Omega (n^{3/2})$. %That is, there are constants $c$ and $n_0$ such that for any $n>n_0$ the size of the smallest defining %set of order $n$ is at least $c{n}^{3/2}$.