The maximum, supremum, and spectrum for critical set sizes in (0,1)‐matrices
Nicholas J. Cavenagh, Liam K. Wright · Journal of Combinatorial Designs · 2019
Abstract If is a partially filled‐in (0,1)‐matrix with a unique completion to a (0,1)‐matrix (with prescribed row and column sums), then we say that is a defining set for . A critical set is a minimal defining set (the deletion of any entry results in more than one completion). We give a new equivalent definition of critical sets in (0,1)‐matrices and apply this theory to , the set of (0,1)‐matrices of dimensions with uniform row and column sum . The smallest possible size for a defining set of a matrix in is [N. Cavenagh, J. Combin. Des. 21 (2013), pp. 253–266], and the infimum (the largest‐smallest defining set size for members of ) is known asymptotically [N. Cavenagh and R. Ramadurai, Linear Algebra Appl. 537 (2018), pp. 38–47]. We show that no critical set of size larger than exists in an element of and that there exists a critical set of size in an element of for each such that . We also bound the supremum (the smallest‐largest critical set size for members of ) between and .