Most binary matrices have no small defining set

Consider a matrix M chosen uniformly at random from a class of m x 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 ε>0, we assume that n≤m=o(n^1+ε), and that λ≤1/2, where λ 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 O(n^1/2+ε), and that the column sums do not vary by more than O(m^1/2+ε). Under these assumptions we show that M almost surely has no defining set of size less than λ mn-O(m^7/4+ε). It follows that M almost surely has no critical set of size more than (1-λ)mn+O(m^7/4+ε). Our results generalise a theorem of Cavenagh and Ramadurai, who examined the case when λ=1/2 and n=m=2^k for an integer k.