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