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.


Nicholas Cavenagh

Research Area

University of Waikato


Tue, 08/08/2017 - 1:00pm to 2:00pm


RC-4082, The Red Centre, UNSW