On the completion of $\epsilon$-dense partial Latin squares

Abstract

A partial Latin square of order $n$ is called $\epsilon$-dense if each row and each column contains at most $\epsilon n$ filled cells, and each symbol occurs at most $\epsilon n$ times. A partial Latin square is said to be completable if its empty cells can be filled to obtain a Latin square. Daykin and Häggkvist conjectured that every $\frac{1}{4}$-dense partial Latin square is completable. In this paper, we show that for all sufficiently large integers $n$, every $\frac{2}{25}$-dense partial Latin square of order $n$ is completable. The proof is obtained by establishing that there exists an $\eta >0$ such that every triangle-divisible balanced tripartite graph on $3n$ vertices with partite minimum degree at least $(\frac{23}{25}-\eta )n$ admits a fractional triangle decomposition.