Title: The minimum size of critical sets in latin squares
Authors: Fu, CM
Fu, HL
Rodger, CA
Department of Applied Mathematics
Keywords: latin squares;critical sets;design construction
Issue Date: 15-Aug-1997
Abstract: 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 1/4n(2), though to date the best-known lower bound is that s(n)greater than or equal to n+1. In this paper, we obtain some conditions on C which force s(C)greater than or equal to[(n-1)/2](2). For n > 20, this is used to show that in generals(n)greater than or equal to[(7n-3)/6], thus improving the best-known result. (C) 1997 Elsevier Science B.V.
URI: http://hdl.handle.net/11536/366
ISSN: 0378-3758
Volume: 62
Issue: 2
Begin Page: 333
End Page: 337
Appears in Collections:Articles

Files in This Item:

  1. A1997XR82100013.pdf