Defining sets and critical sets in (0,1)-matrices.

Abstract

If D is a partially filled-in (0, 1)-matrix with a unique completion to a (0, 1)-matrix M (with prescribed row and column sums), we say that D is a defining set for M. If the removal of any entry of D destroys this property (i.e. at least two completions become possible), we say that D is a critical set for M. In this note, we show that the complement of a critical set for a (0, 1)-matrix M is a defining set for M. We also study the possible sizes (number of filled-in cells) of defining sets for square matrices M with uniform row and column sums, which are also frequency squares. In particular, we show that when the matrix is of even order 2m and the row and column sums are all equal to m, the smallest possible size of a critical set is precisely m². We give the exact structure of critical sets with this property.