The maximum, spectrum and supremum for critical set sizes 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 {\em defining set} for $M$. A {\em critical set} is a minimal defining set (the deletion of any entry results in more than one completion). We give a new classification of critical sets in $(0,1)$-matrices and apply this theory to ${\Lambda }_{2m}^m$, the set of $(0,1)$-matrices of dimensions $2m\times 2m$ with uniform row and column sum $m$. The smallest possible size for a defining set of a matrix in ${\Lambda }_{2m}^m$ is $m^2$ \cite{Cav}, and the infimum (the largest smallest defining set size for members of ${\Lambda }_{2m}^m$) is known asymptotically \cite{CR}. We show that no critical set of size larger than $3m^2-2m$ exists in an element of ${\Lambda }_{2m}^m$ and that there exists a critical set of size $k$ in an element of ${\Lambda }_{2m}^m$ for each $k$ such that $m^2\le k\le 3m^2-4m+2$. We also bound the supremum (the smallest largest critical set size for members of ${\Lambda }_{2m}^m$) between $\lceil (3m^2-2m+1)/2\rceil$ and $2m^2-m$.