Forbidden submatrices (Q1103620): Difference between revisions

We consider an \(m\times n\) (0,1)-matrix A, no repeated columns, which has no \(k\times \ell\) submatrix F. We may deduce bounds on n, polynomial in m, depending on F. The best general bound is \(O(m^{2k-1})\). We improve this and provide best possible bounds for \(k\times 1\) F's and certain \(k\times 2\) F's. In the case that all columns of F are the same, good bounds are obtained which are best possible for \(\ell =2\) and some other cases. Good bounds for \(1\ell \ell\) F's are provided, namely \(n\leq (\ell -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\times 2\) possibilities for F, solving all but 3.