Friday, January 8, 2010
3:30 pm, MC 5158

Richard Anstee
University of British Columbia

Forbidden Configurations: a survey

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