Daykin–Häggkvist partial Latin square completion conjecture
A partial Latin square of order is an array whose entries are symbols from , with no symbol repeated in any row or column, while some cells may be empty. A completion is a Latin square obtained by filling all empty cells while preserving the existing entries.
Daykin–Häggkvist conjecture. Given a partial Latin square of order in which each row, column, and symbol is used at most times, it is possible to complete into a Latin square of order .
The conjecture is a completion form of triangle-decomposition theory for complete tripartite graphs. The source discusses later results giving a weaker asymptotic bound of roughly , so the stated threshold remains open.
References
Primary source
Stefan Glock, Daniela Kühn and Deryk Osthus, “Extremal aspects of graph and hypergraph decomposition problems”, arXiv:2008.00926 (2021).
Progress summary
A September 2026 manuscript improves the best known completion guarantee but does not reach the conjectured one-quarter threshold, so the problem remains open.
Daykin and Häggkvist conjectured in 1983 that every partial Latin square whose rows, columns, and symbols each occur at most times can be completed. The conjectured threshold is sharp: larger densities can fail.
Known results
- Bartlett proved completability at density .
- Bowditch and Dukes, and independently Barber, Kühn, Lo, Osthus, and Taylor, raised the guarantee to roughly .
- A 2016 result established an asymptotic guarantee of .
- Yu and Feng later raised the stated bound to .
September 2026 improvement
Allsop, Bowtell, Lesgourgues, and Petrova report a sufficient threshold of , substantially closer to . Their manuscript is unrefereed and does not prove the conjecture.
Current status (as of September 2026): The conjecture remains open; a new unrefereed manuscript claims completability up to .
Solutions 0
No solutions have been posted yet.