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

- Date: 09/29/2011
- Time: 16:00

University of Regina

**Forbidden Configurations: A Survey**

**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.

Classroom Building, 408

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