Teaching dimension, VC dimension, and critical sets in Latin squares

2016/05/31 by Hamed Hatami, Hatami, Hamed, Yingjie Qian +1
Computer Science · Engineering · #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Machine Learning and Algorithms #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1606.00032

openalex publication_date 2016/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A critical set in an n × n Latin square is a minimal set of entries that uniquely identifies it among all Latin squares of the same size. It is conjectured by Nelder in 1979, and later independently by Mahmoodian, and Bate and van Rees that the size of the smallest critical set is \lfloor n²/4\rfloor. We prove a lower-bound of n²/10⁴ for sufficiently large n, and thus confirm the quadratic order predicted by the conjecture. We prove a lower-bound of n²/10⁴ for sufficiently large n, and thus confirm the quadratic order predicted by the conjecture. This improves a recent lower-bound of Ω(n^3/2) due to Cavenagh and Ramadurai. From the point of view of computational learning theory, the size of the smallest critical set corresponds to the minimum teaching dimension of the set of Latin squares. We study two related notions of dimension from learning theory. We prove a lower-bound of n²-(e+o(1))n^5/3 for both of the VC-dimension and the recursive teaching dimension.

Related

• A new bound on the size of the largest critical set in a Latin square
• On the distances between Latin squares and the smallest defining set size
• Lower bounds on the sizes of defining sets in full n-Latin squares and\n full designs
• Distance in Latin Squares
• Canonical labelling of Latin squares in average-case polynomial time