On completing partial Latin squares with prescribed diagonals (Q2170804)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On completing partial Latin squares with prescribed diagonals
scientific article

    Statements

    On completing partial Latin squares with prescribed diagonals (English)
    0 references
    0 references
    0 references
    0 references
    6 September 2022
    0 references
    Let \(L\) be an \(n\times n\) matrix in which each cell contains a symbol from a set \(S\) with \(|S|=t\). Then \(L\) is a Latin array if no symbol is repeated within any row or within any column. We say that \(L\) is embedded in a Latin square \(T\) on the symbol set \(S\) if \(T(i,j)=L(i,j)\) for \(1\le i,j\le n\). If, in addition, we specify the value of \(T(i,i)\) for every \(i\) in the range \(n<i\le t\), then we say that \(L\) has been embedded in \(T\) with prescribed diagonal. Let \(N(s)\) denote the number of times that symbol \(s\) occurs in \(L\) and let \(f(s)=|\{i:n<i\le t\text{ and }T(i,i)=s\}|\). This paper proves an old conjecture of the last author by showing that if \(f(s)\ne 1\) for all \(s\) then \(L\) can be embedded with a prescribed diagonal if and only if \(N(s)\ge 2n-t+f(s)\) for each \(s\in S\). Examples from \textit{L. D. Andersen} et al. [Ann. Discrete Math. 17, 19--31 (1983; Zbl 0522.05013)] show that the condition requiring \(f(s)\ne1\) cannot be abandoned and that no simple numerical condition characterises embeddability when we allow \(f(s)=1\).
    0 references
    Latin array
    0 references
    idempotent
    0 references
    incomplete Latin square
    0 references
    embedding
    0 references

    Identifiers