Presented by: 
Nicholas Cavenagh (Waikato University)
Date: 
Wed 15 Nov, 1:00 pm - 2:00 pm
Venue: 
Priestley 67-442

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 defining set for M . Let A2m be the set of (0, 1)-matrices of dimensions 2m x 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 A2m is precisely m2. In this note when m is a power of two we construct an element of A2m which has no defining set of size less than 2m2 − o(m2). Given that it is easy to show any A2m has a defining set of size at most 2m2, this construction is asymptotically optimal. Our construction is based on an array, defined using linear algebra, in which any subarray has asymptotically the same number of 0’s and 1’s.