On Forbidden Submatrices

Abstract

Given a $k\times l$ $(0,1)$-matrix $F$, we denote by $\mathrm{fs}(m,F)$ the largest number for which there is an $m\times \mathrm{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 $\mathrm{fs}(m,F)=O(m^k)$ for a fixed matrix $F$. The main results of this paper are that $\mathrm{fs}(m,F)=m^{2+o(1)}$ if $k=2$ and that $\mathrm{fs}(m,F)=m^{5k/3-1+o(1)}$ if $k\ge 3$.

arXiv comment11 pages