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