Latin squares with bounded size of row prefix intersections
A latin square is a matrix of size nn n  n with entries from the set {1,,n} { 1 ,  , n } , such that each row and each column is a permutation on {1,,n} { 1 ,  , n } . We show how to construct a latin square such that for any two distinct rows, the prefixes of length h h of the two rows share at most about h2/n h 2 / n elements. This upper bound is close to optimal when contrasted with a lower bound derived from the Second Johnson bound [6].
latin squares second johnson bound combinatorial design theory coding theory graph theory graph coloring youden squares