A lower bound for the size of the largest critical sets in Latin squares

Abstract

A critical set in an $n\times n$ array is a set $C$ of given entries, such that there exists a unique extension of $C$ to an $n\times n$ Latin square and no proper subset of $C$ has this property. The cardinality of the largest critical set in any Latin square of order $n$ is denoted by $\lcs{n}$. We give a lower bound for $\lcs{n}$ by showing that $\lcs{n} \geq n^2(1-\frac{2 + \ln 2}{\ln n})+n(1+\frac {\ln (8 π)} {\ln n})-\frac{\ln 2}{\ln n}.$

Cited by in corpus (2)

• Latin squares and their defining sets
• On the size of the minimum critical set of a Latin square