Exact Bounds for Forbidden Configurations
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
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
Speakers
Additional Information
Discrete Math Seminar 2007
Farzin Barekat (University of British Columbia)
Farzin Barekat (University of British Columbia)