Towards a solution of the Dinitz problem? (Q1118600)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Towards a solution of the Dinitz problem? |
scientific article |
Statements
Towards a solution of the Dinitz problem? (English)
0 references
1989
0 references
The Dinitz problem may be stated as follows: Given an \(m\times m\) array of m-sets, is it always possible to choose one element from each set so that the chosen elements are distinct in each row and column? Using some elementary properties of graph theory, the author partially resolves this problem by proving that if L is an \(r\times n\) array of n-sets with \(r\leq (2n)/7\), then L contains an \(r\times n\) Latin rectangle.
0 references
Latin rectangle
0 references
Dinitz problem
0 references