Seminar at SMU 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.