PIMS Distinguished Lecture Series: Professor Richard Anstee (University of British Columbia)

Abstract:

Problems in extremal set theory take the form of determining the maximum number of subsets of {1,2, ..., m } you can choose so that the resulting family of subsets has some property. The property I will consider is a trace being forbidden (in hypergraph terms a subhypergraph being forbidden). An incidence matrix encodes the system of subsets as an m-rowed (0,1)-matrix A with no repeated columns. The forbidden trace becomes a 'forbidden configuration' namely for some given (0,1)-matrix F you are forbidding A from having any submatrix which is a row and column permutation of F.

One defines forb(m,F) as the maximum number of columns, over all m-rowed (0,1)-matrices with no repeated column and no submatrix which is a row and column permutation of F. This concept of forbidden configurations appears in a variety of problems of which the study of VC-dimension has been the most notable. I will discuss a number of the bounds obtained and the interesting variety of proofs.