Forbidden configurations and repeated induction

For a given k × ℓ matrix F , we say a matrix A has no configuration F if no k × ℓ submatrix of A is a row and column permutation of F . We say a matrix is simple if it is a (0,1)-matrix with no repeated columns. We define forb ( m , F ) as the maximum number of columns in an m -rowed simple matrix which has no configuration F . A fundamental result of Sauer, Perles and Shelah, and Vapnik and Chervonenkis determines forb ( m , K k ) exactly, where K k denotes the k × 2 k simple matrix. We extend this in several ways. For two matrices G , H on the same number of rows, let [ G ∣ H ] denote the concatenation of G and H . Our first two sets of results are exact bounds that find some matrices B , C where forb ( m , [ K k ∣ B ] ) = forb ( m , K k ) and forb ( m , [ K k ∣ K k ∣ C ] ) = forb ( m , [ K k ∣ K k ] ) . Our final result provides asymptotic boundary cases; namely matrices F for which forb ( m , F ) is O ( m p ) yet for any choice of column α not in F , we have forb ( m , [ F ∣ α ] ) is Ω ( m p + 1 ) . 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 k -rowed (0,1)-matrix F , we also consider a function req ( m , F ) which is the minimum number of columns in an m -rowed simple matrix for which each k -set of rows contains F as a configuration.