On the Existence of Retransmission Permutation Arrays

We investigate retransmission permutation arrays (RPAs) that are motivated by applications in overlapping channel transmissions. An RPA is an n×n array in which each row is a permutation of {1,...,n}, and for 1≤i≤n, all n symbols occur in each i×ceil(n/i) rectangle in specified corners of the array. The array has types 1, 2, 3 and 4 if the stated property holds in the top left, top right, bottom left and bottom right corners, respectively. It is called latin if it is a latin square. We show that for all positive integers n, there exists a type-1,2,3,4 RPA(n) and a type-1,2 latin RPA(n).

As a tool for our construction we prove a lemma that strengthens Hall's theorem about extensions of latin rectangles. Define f_k,n to be the largest integer l<n such that it is possible to complete every n×n partial latin square consisting of k filled rows together with l filled cells in another row. We show that f_k,n=n-2k if 1≤k<n/2, and f_k,n=1 if n/2≤k≤n-2.