A combinatorial theory of higher-dimensional permutation arrays (Q1585504)

This charmingly written paper, packed with examples, introduces a \(d\)-dimensional generalization of permutation matrices, called permutation arrays, via the concept of totally rankable dot arrays. The rank array of permutation arrays is then characterized, and an algorithm for constructing permutation arrays is given. A lower bound for the number of permutation arrays is obtained from sparse arrays, while an upper bound for three-dimensional permutation arrays is found from the algorithm described earlier. However, specific formulas are found for the specializations of permutation arrays that correspond to permutations and set partitions. Finally it is observed that in these situations, a given partial order on permutation arrays yields a poset isomorphic to the Bruhat order on the symmetric group or the partition lattice on an \(n\)-set, respectively.