UVic Discrete Math Seminar: Peter Dukes

Given two $n \times n$ latin squares $L$ and $M$, define their intersection size as the number of common entries when the squares are overlayed: $|\{(i,j) \in [n]^2:L_{ij}=M_{ij}\}|$. The set of all possible intersection sizes between two $n \times n$ latin squares on the same set of symbols was determined long ago in the 1980s. Roughly speaking, most values from $0$ to $n^2$ are achievable, except for a few values near the upper end.

Suppose $n=hw$, where $h$ and $w$ are integers with $h,w \ge 2$. We determine the set of possible intersection numbers of two $n \times n$ Sudoku latin squares having the additional constraint of `distinct symbols in every box’ based on a $w \times h$ grid of $h \times w$ boxes. It turns out that all of the intersection values as for unrestricted latin squares are still achievable in the Sudoku setting.

This is joint work with student author Jade Davies.