Tutte seminar - Richard Anstee

Friday, January 8, 2010 3:30 pm - 4:30 pm EST (GMT -05:00)

Forbidden Configurations: a survey

Speaker: Richard Anstee
Affiliation: University of British Columbia
Room: Mathematics & Computer Building (MC) 5158


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.