A defining set for an array is a partially filled-in array with precisely one completion subject to some kind of combinatorial constraint. (For example, a Sudoku puzzle!) We examine what is known about the defining sets of two quite different arrays: Latin squares and (0,1)-matrices. Intriguingly, while these designs may superficially seem quite different, empirical evidence suggests that in certain cases they have the same minimum defining set size: exactly one quarter of the total size of the design. We call this ratio the surety of a type of design; thus Latin squares are conjectured to have a surety of 1/4. We show that a 2m x 2m (0,1)-matrix with constant row and column sum m has surety equal to 1/4 and explain why a problem which appears difficult to solve for Latin squares becomes tractable for (0,1)-matrices.


Nick Cavanagh

Research Area

Pure Maths Seminar


The University of Waikato


Tue, 03/04/2012 - 12:00pm to 1:00pm


RC-4082, Red Centre Building, UNSW