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 t here exists a unique extension of C to an n x n Latin square and no proper subset of C has t his property. T he cardina lity of t he la rgest critical set in any Latin square of order n is denoted by lcs(n). We give a lower bound for lcs(n) by showing t hat lcs(n) 2- n2(1 _ 2+ln 2) + n( l + ln(81r)) _ hl. . In n In n Inn