Covering with Latin transversals (Q1345959): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 14:48, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Covering with Latin transversals |
scientific article |
Statements
Covering with Latin transversals (English)
0 references
11 July 1995
0 references
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\).
0 references
covering
0 references
Latin transversal
0 references
square matrix
0 references
probabilistic method
0 references
Lovász local lemma
0 references