Department of Mathematics, University of Waikato

2011-11-24

G.3.33

A defining set for a design is a subset of the design which determines it uniquely. We examine what is known about the defining sets of two quite different designs: 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 columns 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.

We also briefly explore the notion of surety and its generalizations as comparative tools for analysing designs.

(I am afraid this talk will be up to 50 minutes long as it is a practice talk for a conference in December, however participants will be awarded (ginger) beer afterwards....)