Forbidden configurations

In this work we explore the field of Forbidden Configurations, a problem in Extremal Set Theory. We consider a family of subsets of {1,2,...,m} as the corresponding {0,1}-incidence matrix. For {0,1}-matrices F, A, we say F is a *subconfiguration* of A if A has a submatrix which is a row and column permutation of F. We say a {0,1}-matrix is *simple* if it has no repeated columns. Let ||A|| denote the number of columns of A. A {0,1}-matrix F with row and column order stripped is a *configuration*. Given m and a family of configurations G, our main function of study is forb(m,G) := max{||A|| : A simple and for all F in G, we have F not a subconfiguration of A }. We give a general introduction to the main ideas and previous work done in the topic. We develop a new more computational approach that allows us to tackle larger problems. Then we present an array of new results, many of which were solved in part thanks to the new computational approach.Science, Faculty ofMathematics, Department ofGraduat