Theoretical Statistics and Mathematics Unit, ISI Delhi

February 29, 2012 (Wednesday) ,
3:30 PM at Webinar

Speaker:
Niranjan Balachandran,
Indian Institute of Technology, Bombay

Title:
Forbidden configurations and Steiner designs

Abstract of Talk

Let F be a (0,1) matrix. A (0,1) matrix M is said
to have F as a configuration if there is a submatrix
of M which is a row and column permutation of F. We
say that a matrix M is simple if it has no repeated
columns. For a given $v\in \mathbb{N}$, we shall denote by
forb(v,F) the maximum number of columns in a simple
(0,1) matrix with v rows for which F does not occur
as a configuration. We show that for certain
natural choices of F, forb(v,F)
$\leq\frac{\binom{v}{t}}{t+1}$. In particular this
gives an extremal characterization for Steiner
t-designs as maximal (0,1) matrices in terms of
certain forbidden configurations, and our bound is
asymptotically tight. In particular, this answers a
question posed by Richard Anstee.