Given a k x l (0,1)-matrix F, we denote by fs(m, F) the largest number for which there is an m x fs(m, F) (0,1)-matrix with no repeated columns and no induced submatrix equal to F. A conjecture of Anstee, Frankl, Furedi 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+om (1))) and for k >= 3 that fs(m, F) = O(m((5/3)k-1+om (1))). (C) 2014 Elsevier Inc. All rights reserved.
展开▼
