Exact Bounds for Forbidden Configurations

  • Date: 09/18/2007
Lecturer(s):

Farzin Barekat (University of British Columbia)

Location: 

University of British Columbia

Topic: 

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

Other Information: 

Discrete Math Seminar 2007

Sponsor: 

pims