A Latin square is an n x n array of symbols {0,1,...,nâ1} in which each symbol occurs precisely once in each row and once in each column. In this talk, we show that for each Latin square L of order n, there exists a Latin square L', not equal to L, of order n such that L and L' differ in at most 8sqrt(n) cells. Note that a trivial upper bound is 2n, obtained simply by swapping any pair of rows. While it is conjectured to be of the order O(log n), our result is the first upper bound which is o(n).

We also improve previous bounds on the size of the smallest defining set in a Latin square and show that it is at least cn^{3/2} with c a constant, where a defining set is a partial Latin square which has a unique completion to a Latin Square.