A generalisation of transversals for Latin squares

We define a k-plex to be a partial latin square of order n containing kn entries such that exactly k entries lie in each row and column and each of n symbols occurs exactly k times. A transversal of a latin square corresponds to the case k=1. For k>n/4 we prove that not all k-plexes are completable to latin squares. Certain latin squares, including the Cayley tables of many groups, are shown to contain no (2c+1)-plex for any integer c. However, Cayley tables of soluble groups have a 2c-plex for each possible c. We conjecture that this is true for all latin squares and confirm this for orders n≤8. Finally, we demonstrate the existence of indivisible k-plexes, meaning that they contain no c-plex for 1≤c<k.

Click here to download the whole paper.