Most binary matrices have no small defining set

Abstract

Consider a matrix $M$ chosen uniformly at random from a class of $m\times n$ matrices of zeros and ones with prescribed row and column sums. A partially filled matrix $D$ is a $defining$ $set$ for $M$ if $M$ is the unique member of its class that contains the entries in $D$. The $size$ of a defining set is the number of filled entries. A $critical$ $set$ is a defining set for which the removal of any entry stops it being a defining set. For some small fixed $\epsilon >0$, we assume that $n\le m=o(n^{1+\epsilon })$, and that $\lambda \le 1/2$, where $\lambda$ is the proportion of entries of $M$ that equal $1$. We also assume that the row sums of $M$ do not vary by more than $\mathcal{O}(n^{1/2+\epsilon })$, and that the column sums do not vary by more than $\mathcal{O}(m^{1/2+\epsilon })$. Under these assumptions we show that $M$ almost surely has no defining set of size less than $\lambda mn-\mathcal{O}(m^{7/4+\epsilon })$. It follows that $M$ almost surely has no critical set of size more than $(1-\lambda )mn+\mathcal{O}(m^{7/4+\epsilon })$. Our results generalise a theorem of Cavenagh and Ramadurai, who examined the case when $\lambda =1/2$ and $n=m=2^k$ for an integer $k$.