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 Pab and Pcd are occupied by the same
symbol the `opposite corners' Pad and Pbc are
blank. We show that, as the order n of the partial latin square
increases, a density of at least \exp\left(-c(\log n)^{1/2}\right) 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
(\sqrt{11}-1)(1+4/n)/5 is not possible.
Last modified: Wed Sep 8 13:43:13 EST 2004