Presenter: Nicholas Cavenagh, Waikato University

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.

About Pure mathematics seminars

We present regular seminars on a range of pure mathematics interests. Students, staff and visitors to UQ are welcome to attend, and to suggest speakers and topics.

Seminars are usually held on Tuesdays from 3pm to 3.50pm.

Talks comprise 45 minutes of speaking time plus five minutes for questions and discussion.

Information for speakers

Researchers in all pure mathematics fields attend our seminars, so please aim your presentation at a general mathematical audience.

Contact us

To volunteer to talk or to suggest a speaker, email Ole Warnaar or Ramiro Lafuente.


Priestley (67)