On generalized Howell designs with block size three

• Published in: Designs, codes, and cryptography codes, and cryptography, 2016-11, Vol.81 (2), p.365-391
• Main Authors: Abel, R. Julian R., Bailey, Robert F., Burgess, Andrea C., Danziger, Peter, Mendelsohn, Eric
• Format: Article
• Language: English
• Subjects: Circuits; Coding and Information Theory; Computer Science; Cryptology; Data Structures and Information Theory; Discrete Mathematics in Computer Science; Information and Communication
• ISSN: 0925-1022; 1573-7586
• DOI: 10.1007/s10623-015-0162-7

In this paper, we examine a class of doubly resolvable combinatorial objects. Let t , k , λ , s and v be nonnegative integers, and let X be a set of v symbols. A generalized Howell design , denoted t - GHD k ( s , v ; λ ) , is an s × s array, each cell of which is either empty or contains a k -set of symbols from X , called a block , such that: (i) each symbol appears exactly once in each row and in each column (i.e. each row and column is a resolution of X ); (ii) no t -subset of elements from X appears in more than λ cells. Particular instances of the parameters correspond to Howell designs, doubly resolvable balanced incomplete block designs (including Kirkman squares), doubly resolvable nearly Kirkman triple systems, and simple orthogonal multi-arrays (which themselves generalize mutually orthogonal Latin squares). Generalized Howell designs also have connections with permutation arrays and multiply constant-weight codes. In this paper, we concentrate on the case that t = 2 , k = 3 and λ = 1 , and write GHD ( s , v ) . In this case, the number of empty cells in each row and column falls between 0 and ( s - 1 ) / 3 . Previous work has considered the existence of GHDs on either end of the spectrum, with at most 1 or at least ( s - 2 ) / 3 empty cells in each row or column. In the case of one empty cell, we correct some results of Wang and Du, and show that there exists a GHD ( n + 1 , 3 n ) if and only if n ≥ 6 , except possibly for n = 6 . In the case of two empty cells, we show that there exists a GHD ( n + 2 , 3 n ) if and only if n ≥ 6 . Noting that the proportion of cells in a given row or column of a GHD ( s , v ) which are empty falls in the interval [0, 1 / 3), we prove that for any π ∈ [ 0 , 5 / 18 ] , there is a GHD ( s , v ) whose proportion of empty cells in a row or column is arbitrarily close to π .