Towards a solution of the Dinitz problem? (Q1118600)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Towards a solution of the Dinitz problem? |
scientific article; zbMATH DE number 4095474
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Towards a solution of the Dinitz problem? |
scientific article; zbMATH DE number 4095474 |
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