On forbidden submatrices

Given a k×lk×l(0,1)(0,1)-matrix F  , we denote by fs(m,F)fs(m,F) the largest number for which there is an m×fs(m,F)m×fs(m,F)(0,1)(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(mk)fs(m,F)=O(mk). The main results of this paper are that for k=2k=2, fs(m,F)=O(m2+om(1))fs(m,F)=O(m2+om(1)) and for k≥3k≥3 that fs(m,F)=O(m(5/3)k−1+om(1))fs(m,F)=O(m(5/3)k−1+om(1)).