Completing partial Latin squares with two filled rows and three filled columns (Q2167566)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Completing partial Latin squares with two filled rows and three filled columns
scientific article

    Statements

    Completing partial Latin squares with two filled rows and three filled columns (English)
    0 references
    0 references
    0 references
    25 August 2022
    0 references
    Consider an \(n\times n\) array some of whose cells have been filled with at most one symbol from \([n]=\{1,2,\ldots ,n\}\). It is a partial Latin square if no symbol occurs more than once in any row or column. It is a Latin square if no cell is unfilled (and more generally an \(r\times s\) Latin rectangle, where \(\max \{r,s\}=n\), is an \(r\times s\) array whose entries have been filled with entries from \([n]\) in such a way that no symbol occurs more than once in any row or column. It has been a long-standing question about when a partial Latin square is completable, i.e. it can be completed to a Latin square, i.e. a Latin square that agrees with the partial Latin square on all cells of the partial Latin square which had been filled in. Such questions tend to be hard, both formally and informally. The main aim of the paper under review is to consider the case of partial Latin squares with two completely filled rows and three completely filled columns and all other cells empty. It is a conjecture from [\textit{J. Kuhl} and \textit{D. McGinn}, Australas. J. Comb. 68, Part 2, 186--201 (2017; Zbl 1375.05040)] that any such partial Latin square with \(n\geq 8\) is completeable (the condition \(n\geq 8\) is known to be necessary). In the paper under review, based on the second author's Bachelor's thesis [Completing partial Latin squares with two filled rows and three filled columns. Linköping: Linköpings Universitet (Bachelor Thesis) (2020)], the conjecture is proved in the special case that the \(2\times 3\) intersection of the two filled rows and three filled columns forms a Latin rectangle of order 3, i.e. only uses three symbols. The proof develops further ideas from the paper of Kuhl and McGinn [loc. cit.].
    0 references
    0 references
    Latin square
    0 references
    partial Latin square
    0 references
    completing partial Latin squares
    0 references
    0 references