Covering with Latin transversals (Q1345959): Difference between revisions

A Latin transversal is a set of elements from a square matrix, one from each row and column and no two the same. As the authors note, the supply of conjectures about Latin transversals outstrip the ability to resolve them. In this paper, the authors show that the elements of an \(n\) by \(n\) matrix can be partitioned into \(n\) Latin transversals provided (1) \(n\) is a power of two, and (2) no element appears more than \(pn\) times, for some fixed \(p\). The proof uses the probabilistic method relying on the Lovász local lemma. The authors, of course, add to the supply of unresolved conjectures by suggesting that the result proved should hold for all \(n\).