## Exact Bounds for Forbidden Configurations

- Date: 09/18/2007

Farzin Barekat (University of British Columbia)

University of British Columbia

We explore some exact bounds for Forbidden Configurations,

which have a design theory flavour. Let q be given. Consider an m-rowed

(0,1)-matrix A, which has no repeated columns. Assume there is no qx2

submatrix of A which is a row and column permutation of

11..11

11..11

00..00

Given that m is large with respect to q, we establish the correct upper

bound on the number of columns that A can have, improving quite a bit

on a pigeonhole bound. An existence theorem of Dehon (1983) for simple

triple design is important in establishing that the bound is exact.

We also establish exact bounds for the following cases:

11..11

00..00

11..11

11..11

00..00

00..00

Discrete Math Seminar 2007