Forbidden submatrices

AbstractWe consider a m × n (0, 1)-matrix A, no repeated columns, which has no k × l sumatrix F. We may deduce bounds on n, polynomial in m, depending on F. The best general bound is O(m2k−1). We improve this and provide best possible bounds for k × 1 F's and certain k × 2 F's. In the case that all columns of F are the same, good bounds are obtained which are best possible for l = 2 and some other cases. Good bounds for 1 × l F's are provided, namely n ⩽ (l−1)m + 1, which are shown to be best possible for F = [1010...10]. The paper finishes with a study of the 14 different 3 × 2 possibilities for F, solving all but 3