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