#
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.