Tutte seminar - Richard Anstee

Forbidden Configurations: a survey

Abstract:

Forbidden configurations are a problem in Extremal Set Theory. In matrix terms, a set system is a (0,1)-matrix with no repeated columns, which we call a simple matrix. Consider a fixed (0,1)-matrix F. We say a matrix A has a F as a configuration if a submatrix of A is a row and column permutation of F. We denote forb(m,F) as the maximum number of columns in a m-rowed simple matrix with no configuration F. With Sali, we conjecture the asymptotic behavior of forb(m,F) and we outline some results and proof techniques. 

This talk has joint work with a number of coauthors including Steven Karp of UWaterloo.