Forbidden Configurations: a survey
|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.
200 University Avenue West
Waterloo, ON N2L 3G1