A new bound on the size of the largest critical set in a Latin square

Bean, Richard; Mahmoodian, E. S.

A new bound on the size of the largest critical set in a Latin square

Authors

Description

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). In 1978 Curran and van Rees proved that lcs(n) <= n^2 - n. Here we show that lcs(n) <= n^2-3n+3.
10 pages, LaTeX