On the completability of incomplete Latin squares (Q966163)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On the completability of incomplete Latin squares
scientific article

    Statements

    On the completability of incomplete Latin squares (English)
    0 references
    0 references
    27 April 2010
    0 references
    An \textit{incomplete Latin square} is an \(n \times n\) array where some of the cells have an entry from \(\{1,\dots,n\}\) such that no symbol occurs twice in a row or column. The square is \textit{completable} if it can be extended to a Latin square of the same order. The question is {`Which incomplete Latin squares are completable?'} In this paper the authors examine when an incomplete Latin square has a row that can be completed. They introduce an availability matrix and use the Frobenius-König Theorem to find necessary and sufficient conditions for such a row. They then examine when the incomplete square has two rows that can be extended using the framework of \((1,2)\)-permutations. They consider an integer programming formulation with polyhedral results, and a nice application for class-teacher time-table problems.
    0 references
    incomplete Latin square
    0 references
    completabele Latin square
    0 references
    complete Latin square
    0 references
    integer programming
    0 references
    class teacher time table problem
    0 references

    Identifiers