Premium
On the spectrum of critical sets in latin squares of order 2 n
Author(s) -
Donovan Diane,
LeFevre James,
van Rees G. H. John
Publication year - 2008
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.20144
Subject(s) - latin square , circulant matrix , mathematics , combinatorics , order (exchange) , square (algebra) , abelian group , set (abstract data type) , discrete mathematics , geometry , computer science , rumen , chemistry , food science , finance , fermentation , economics , programming language
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