A Lower Bound for the Size of the Largest Critical Sets in Latin Squares

Abstract

A critical set in an n x n array is a set C of given entries, such that there exists a unique extension of C to an n x 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) ≥ n2(1 _ 2+ln 2/In n) + n( l + ln(8π)/In n) -ln2/Inn