# A partial latin squares problem posed by Blackburn

Blackburn asked for the largest possible density of filled cells in a
partial latin square with the property that whenever two distinct
cells P_{ab} and P_{cd} are occupied by the same
symbol the `opposite corners' P_{ad} and P_{bc} are
blank. We show that, as the order n of the partial latin square
increases, a density of at least exp(-c(log n)^{1/2}) is
possible using a diagonally cyclic construction, where c is a positive
constant. The question of whether a constant density is achievable
remains, but we show that a density exceeding
(√11-1)(1+4/n)/5 is not possible.
Click here to download the whole paper.

Last modified: Wed Sep 8 13:43:13 EST 2004