On generalized Howell designs with block size three

详细信息    查看全文

• 作者：R. Julian R. Abel ; Robert F. Bailey ; Andrea C. Burgess…
• 刊名：Designs, Codes and Cryptography
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：81
• 期：2
• 页码：365-391
• 全文大小：716 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Coding and Information Theory
  Data Structures, Cryptology and Information Theory
  Data Encryption
  Discrete Mathematics in Computer Science
  Information, Communication and Circuits
  
• 出版者：Springer Netherlands
• ISSN：1573-7586
• 卷排序：81

文摘

In this paper, we examine a class of doubly resolvable combinatorial objects. Let \(t, k, \lambda , s\) and v be nonnegative integers, and let X be a set of v symbols. A generalized Howell design, denoted t-\(\mathrm {GHD}_{k}(s,v;\lambda )\), is an \(s\times 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 \(\lambda \) 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 \(\lambda =1\), and write \(\mathrm {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 \(\mathrm {GHD}(n+1,3n)\) if and only if \(n \ge 6\), except possibly for \(n=6\). In the case of two empty cells, we show that there exists a \(\mathrm {GHD}(n+2,3n)\) if and only if \(n \ge 6\). Noting that the proportion of cells in a given row or column of a \(\mathrm {GHD}(s,v)\) which are empty falls in the interval [0, 1 / 3), we prove that for any \(\pi \in [0,5/18]\), there is a \(\mathrm {GHD}(s,v)\) whose proportion of empty cells in a row or column is arbitrarily close to \(\pi \).KeywordsGeneralized Howell designsTriple systemsDoubly resolvable designs