A generalization of transversals for Latin squares (Q5960787)

A \(k\)-plex is a partial Latin square of order \(n\) such that each row and each column has exactly \(k\) cells filled, and each entry occurs precisely \(k\) times. A \(1\)-plex is a transversal, a particularly important notion in the theory of Latin squares (a Latin square has an orthogonal partner if and only if it can be decomposed into transversals). The paper is a detailled study of plexes and includes interesting historical notes. An easy result says that \(k\)-plexes always exist \((k\leq n).\) More challenging is the proof of the fact that for \(k>n/4\) there always exists a \(k\)-plex of order \(n\) which cannot be completed to a Latin square. A conjecture states that this result is sharp (every \(k\)-plex of order \(n\) should be completable if \(k\leq n/4\)). Special cases of Latin squares are multiplication tables of groups. A peculiar situation arises when the group \(G\) has a normal \(2\)-complement. This is the case in particular when the Sylow-\(2\)-subgroup of \(G\) is cyclic. Latin squares of \(q\)-step type are a combinatorial generalization of this situation. The corresponding group tables do not possess any \(k\)-plexes for odd \(k,\) but do possess \(k\)-plexes for all even \(k.\) Rather complete enumeration results are given for plexes in Latin squares of orders up to \(8.\) These results are interesting in the light of a theorem by \textit{K. Balasubramanian} [Linear Algebra Appl. 131, 125-129 (1990; Zbl 0704.05007)] who showed that Latin squares of even order have an even number of transversals. The enumeration in the case of these small orders shows that several conceivable generalizations of this result are not true. This refutes in particular an old conjecture of Ryser stating that each Latin square of odd order has an odd number of transversals. A new conjecture states that each Latin square of even order can be decomposed into \(2\)-plexes.