A critical set C of order n is a partial latin square of order n which is uniquely completable to a latin square, and omitting any entry of the partial latin square destroys this property. The size s(C) of a critical set C is the number of filled cells in the partial latin square. The size of a minimum critical set of order n is s(n). It is likely that s(n) is approximately 14n2, though to date the best-known lower bound is that s(n) ⩾ n + 1. In this paper, we obtain some conditions on C which force s(C) ⩾ [(n − 1)2]2. For n > 20, this is used to show that in general s(n) ⩾ [(7n − 3)6], thus improving the best-known result.
關聯:
Journal of Statistical Planning and Inference 62(2), pp.333-337
