Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 49 min ago
PreprintCC BY 4.0arXiv

A counting proof for the smallest critical set in a Latin square

  • Richard Bean
Open at sourcePDFDOICite

Abstract

A critical set in a Latin square is a set of entries that determines the square uniquely and is minimal with this property. We prove that every partial Latin square of order n with fewer than ⌊ n2/4⌋ filled cells has an even number of completions. Consequently every critical set in every Latin square of order n has at least ⌊ n2/4⌋ entries. Since the cyclic Latin square has a critical set of exactly this size, the minimum size of a critical set over all Latin squares of order n is ⌊ n2/4⌋. This confirms a conjecture attributed to Nelder (1979) and made independently by Mahmoodian and by Bate and van Rees. Hatami and Qian had shown that this minimum is at least n2/104 for large n. The proof is a counting argument modulo two that uses only expansion of products, cancellation in pairs and the pigeonhole principle, and it is illustrated with partial Latin squares of orders three to seven. An appendix discloses the substantial use of AI in developing the proof and writing the exposition.

Related

  1. The smallest square tileable by pairwise incomparable integer rectangles
    George M. Georgiou
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Avoiding a partial Latin square with an isotope of a given Latin square
    Stijn Cambie, Ian M. Wanless
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. A Combinatorial Proof of an Identity of Malik and Sarma on Overpartitions with Repeated Smallest Non-Overlined Part
    Suparno Ghoshal, Arijit Jana
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Counting and constructing Latin tableaux
    Spencer Daugherty, Michaela Fahnesock, Shawn Huxtable +3
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. On the probability that a random Latin square is all-even
    Catherine Greenhill, Lenka Kopfová, Matthew Kwan +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{bean2026counting,
  title = {{A counting proof for the smallest critical set in a Latin square}},
  author = {Richard Bean},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.18199},
  eprint = {2610.18199},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.18199},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - A counting proof for the smallest critical set in a Latin square
AU  - Richard Bean
PY  - 2026
DA  - 2026/10/13
PB  - arXiv
DO  - 10.48550/arxiv.2610.18199
UR  - https://arxiv.org/abs/2610.18199
AB  - A critical set in a Latin square is a set of entries that determines the square uniquely and is minimal with this property. We prove that every partial Latin square of order n with fewer than ⌊ n^2/4⌋ filled cells has an even number of completions. Consequently every critical set in every Latin square of order n has at least ⌊ n^2/4⌋ entries. Since the cyclic Latin square has a critical set of exactly this size, the minimum size of a critical set over all Latin squares of order n is ⌊ n^2/4⌋. This confirms a conjecture attributed to Nelder (1979) and made independently by Mahmoodian and by Bate and van Rees. Hatami and Qian had shown that this minimum is at least n^2/10^4 for large n. The proof is a counting argument modulo two that uses only expansion of products, cancellation in pairs and the pigeonhole principle, and it is illustrated with partial Latin squares of orders three to seven. An appendix discloses the substantial use of AI in developing the proof and writing the exposition.
ER  -