On Forbidden Submatrices

Original · EN

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 fs(m,F) = O(mᵏ) for a fixed matrix F. The main results of this paper are that fs(m,F) = m²⁺ ᵒ⁽¹⁾ if k=2 and that fs(m,F) = m⁵ᵏ/³ ⁻¹ ⁺ ᵒ⁽¹⁾ if k≥ 3.