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(-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