Skip to main content
placeholder image

Critical Sets in Orthogonal Arrays

Journal Article


Abstract


  • A critical set consists of the minimum amount of information needed to recreate combinatorial structures uniquely. A minimal critical set is a critical set of minimum cardinality. In this paper we consider orthogonal arrays constructed from Mutually Orthogonal Latin Squares (MOLS) and obtain bounds on the possible sizes of the minimal critical sets. If there exists a set of k MOLS of order n and each Latin Square has a minimal critical set of size atmost cl, then we show that there is a minimal critical set of size COA, of the corresponding OA(n2, k + 2, n 2) satisfying CQA ≤ kcl. This bound is shown to be exact for n = 3 by actual construction of a minimal critical set. However, for n ≥ 4 this bound can be improved upon. Using the fact that for n = 4 the Latin Square representing the elementary abelian 2-group has a minimal critical set of size 5, and only this form or its isotopic has orthogonal mates, we exhibit a minimal critical set of size 11 for an OA(16,5,4,2). For n > 4, n odd, we consider OA(n2, k + 2,n,2) made from a back circulant Latin Square which is a particular Latin Square having initial row in the standard form and subsequent rows formed by translating the previous row one element to the left. We prove by actual construction, that if the minimal critical set for a back circulant latin square is of size cl, then any of its orthogonal mate can be uniquely reconstructed given information on cl - 1 cells only. Interestingly enough, for n = 5, starting with a minimal critical set of size 6, we construct a minimal critical set of size 18 for a complete set of MOLS and the corresponding orthogonal array. Identification of a critical set for n = 7 is also discussed. © 2005 Elsevier Ltd. All rights reserved.

Publication Date


  • 2003

Citation


  • Critical Sets in Orthogonal Arrays (2003). Electronic Notes in Discrete Mathematics, 15, 160. doi:10.1016/S1571-0653(04)00568-2

Scopus Eid


  • 2-s2.0-34247238347

Web Of Science Accession Number


Start Page


  • 160

Volume


  • 15

Abstract


  • A critical set consists of the minimum amount of information needed to recreate combinatorial structures uniquely. A minimal critical set is a critical set of minimum cardinality. In this paper we consider orthogonal arrays constructed from Mutually Orthogonal Latin Squares (MOLS) and obtain bounds on the possible sizes of the minimal critical sets. If there exists a set of k MOLS of order n and each Latin Square has a minimal critical set of size atmost cl, then we show that there is a minimal critical set of size COA, of the corresponding OA(n2, k + 2, n 2) satisfying CQA ≤ kcl. This bound is shown to be exact for n = 3 by actual construction of a minimal critical set. However, for n ≥ 4 this bound can be improved upon. Using the fact that for n = 4 the Latin Square representing the elementary abelian 2-group has a minimal critical set of size 5, and only this form or its isotopic has orthogonal mates, we exhibit a minimal critical set of size 11 for an OA(16,5,4,2). For n > 4, n odd, we consider OA(n2, k + 2,n,2) made from a back circulant Latin Square which is a particular Latin Square having initial row in the standard form and subsequent rows formed by translating the previous row one element to the left. We prove by actual construction, that if the minimal critical set for a back circulant latin square is of size cl, then any of its orthogonal mate can be uniquely reconstructed given information on cl - 1 cells only. Interestingly enough, for n = 5, starting with a minimal critical set of size 6, we construct a minimal critical set of size 18 for a complete set of MOLS and the corresponding orthogonal array. Identification of a critical set for n = 7 is also discussed. © 2005 Elsevier Ltd. All rights reserved.

Publication Date


  • 2003

Citation


  • Critical Sets in Orthogonal Arrays (2003). Electronic Notes in Discrete Mathematics, 15, 160. doi:10.1016/S1571-0653(04)00568-2

Scopus Eid


  • 2-s2.0-34247238347

Web Of Science Accession Number


Start Page


  • 160

Volume


  • 15