On a Conjecture Concerning Forbidden Submatrices

Abstract

Some extremal set problems can be phrased as follows. Given an $m\times n$ $(0,1)$-matrix $A$ with no repeated columns and with no submatrix of a certain type, what is a bound on $n$ in terms of $m$? We examine a conjecture of Frankl, Füredi, and Pach and the author that when we forbid a $k\times l$ submatrix $F$ then $n$ is $O(m^k)$. Two proof techniques are presented, one is amortized complexity and the other uses a result of Alon to show that $n$ is $O(m^{2k-1-ϵ})$ for $ϵ=(k-1)/(13{\log }_{2}l)$, improving on the previous bound of $O(m^{2k-1})$.