Packing arrays

A packing array is a b×k array of values from a g-ary alphabet such that given any two columns, i and j, and for all ordered pairs of elements from the g-ary alphabet, (g 1, g 2), there is at most one row, r, such that a r, i =g 1 and a r, j =g 2. A central question is to determine, for given g and k, the maximum possible b. We develop general direct and recursive constructions and upper bounds on the sizes of packing arrays. We introduce the consideration of a set of disjoint rows in a packing array which allows these constructions and additionally gives a new upper bound on the size of all packing arrays. We also show the equivalence of the problem to a matching problem on graphs and a class of resolvable pairwise balanced designs. We provide tables of the best known upper and lower bounds.

Authors

• Brett Stevens
• Eric Mendelsohn

Keywords

• Orthogonal arrays
• Transversal designs
• Packing arrays
• MDS codes
• Matchings
• Partial latin squares
• Partial match queries