The minimum size of critical sets in latin squares

Chin Mei Fu, Hung-Lin Fu, C. A. Rodger*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

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/4n2, 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.

Original languageEnglish
Pages (from-to)333-337
Number of pages5
JournalJournal of Statistical Planning and Inference
Volume62
Issue number2
DOIs
StatePublished - 15 Aug 1997

Keywords

  • Critical sets
  • Design construction
  • Latin squares

Fingerprint Dive into the research topics of 'The minimum size of critical sets in latin squares'. Together they form a unique fingerprint.

Cite this