Forbidden configurations and repeated induction

Abstract: For a given matrix , we say a matrix has no configuration if no submatrix of is a row and column permutation of . We say a matrix is simple if it is a (0,1)-matrix with no repeated columns. We define as the maximum number of columns in an -rowed simple matrix which has no configuration . A fundamental result of Sauer, Perles and Shelah, and Vapnik and Chervonenkis determines exactly, where denotes the simple matrix. We extend this in several ways. For two matrices on the same number of rows, let denote the concatenation of and . Our first two sets of results are exact bounds that find some matrices where and . Our final result provides asymptotic boundary cases; namely matrices for which is yet for any choice of column not in , we have is . This is evidence for a conjecture of Anstee and Sali. The proof techniques in this paper are dominated by repeated use of the standard induction employed in forbidden configurations. Analysis of base cases tends to dominate the arguments. For a -rowed (0,1)-matrix , we also consider a function which is the minimum number of columns in an -rowed simple matrix for which each -set of rows contains as a configuration. [Copyright &y& Elsevier]