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

  • Date: 09/29/2011
  • Time: 16:00
Richard Anstee, University of British Columbia

University of Regina


Forbidden Configurations: A Survey



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.

Other Information: 

Classroom Building, 408


For further information, please see the event page at: http://www.uregina.ca/science/mathstat/lectures.html.