Constructing (0,1)-matrices with large minimal defining sets

Abstract: 

If DD is a partially filled-in (0,1)(0,1)-matrix with a unique completion to a (0,1)(0,1)-matrix MM (with prescribed row and column sums), we say that DD is a defining set for MM . Let A2mA2m be the set of (0, 1)-matrices of dimensions 2m×2m2m×2m with uniform row and column sum m. It is shown in (Cavenagh, 2013) that the smallest possible size for a defining set of an element of A2mA2m is precisely m2m2. In this note when m is a power of two we construct an element of A2mA2m which has no defining set of size less than 2m2−o(m2)2m2−o(m2). Given that it is easy to show any A2mA2m has a defining set of size at most 2m22m2, this construction is asymptotically optimal. Our construction is based on a array, defined using linear algebra, in which any subarray has asymptotically the same number of 0’s and 1’s.  This is joint work with Reshma Ramadurai.