On the spectrum of critical sets in latin squares of order 2n

✍ Scribed by Diane Donovan; James LeFevre; G. H. John van Rees

• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 197 KB
• Volume: 16
• Category: Article
• ISSN: 1063-8539
• DOI: 10.1002/jcd.20144

✦ Synopsis

Abstract

Suppose that L is a latin square of order m and P ⊑ L is a partial latin square. If L is the only latin square of order m which contains P, and no proper subset of P has this property, then P is a critical set of L. The critical set spectrum problem is to determine, for a given m, the set of integers t for which there exists a latin square of order m with a critical set of size t. We outline a partial solution to the critical set spectrum problem for latin squares of order 2^n^. The back circulant latin square of even order m has a well‐known critical set of size m^2^/4, and this is the smallest known critical set for a latin square of order m. The abelian 2‐group of order 2^n^ has a critical set of size 4^n^‐3^n^, and this is the largest known critical set for a latin square of order 2^n^. We construct a set of latin squares with associated critical sets which are intermediate between the back circulant latin square of order 2^n^ and the abelian 2‐group of order 2^n^. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 25–43, 2008