On forbidden submatrices.

Given a k × l ( 0 , 1 ) -matrix F , we denote by fs ( m , F ) the largest number for which there is an m × fs ( m , F ) ( 0 , 1 ) -matrix with no repeated columns and no induced submatrix equal to F . A conjecture of Anstee, Frankl, Füredi and Pach states that, regarding F as fixed, fs ( m , F ) = O ( m k ) . The main results of this paper are that for k = 2 , fs ( m , F ) = O ( m 2 + o m ( 1 ) ) and for k ≥ 3 that fs ( m , F ) = O ( m ( 5 / 3 ) k − 1 + o m ( 1 ) ) . [ABSTRACT FROM AUTHOR]