Item

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.
Type
Journal Article
Type of thesis
Series
Citation
Cavenagh, N. J. (2013). Defining Sets and Critical Sets in (0,1)-Matrices. Journal of Combinatorial Designs, 21(6), 253-266.
Date
2013
Publisher
Wiley Periodicals, Inc
Degree
Supervisors
Rights