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
    0 references
    0 references

    Identifiers