On the distances between Latin squares and the smallest defining set size

2016/02/24 by Nicholas Cavenagh, Cavenagh, Nicholas, Reshma Ramadurai +1 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1602.07734

arxiv created 2016/02/24 · arxiv updated 2016/02/26

Abstract

In this note we show that for each Latin square L of order n≥ 2, there exists a Latin square L'≠ L of order n such that L and L' differ in at most 8√(n) cells. Equivalently, each Latin square of order n contains a Latin trade of size at most 8√(n). We also show that the size of the smallest defining set in a Latin square is Ω(n^3/2). %That is, there are constants c and n₀ such that for any n>n₀ the size of the smallest defining %set of order n is at least cn^3/2.

Cited by

• Parities in random Latin squares

Related

• Distance in Latin Squares
• Lower bounds on the sizes of defining sets in full n-Latin squares and\n full designs
• Teaching dimension, VC dimension, and critical sets in Latin squares
• Latin squares and their defining sets
• Substructures in Latin squares