On a Conjecture Concerning Forbidden Submatrices

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-\epsilon})\) for \(\epsilon=(k-1)/(13 \log_2 l)\), improving on the previous bound of \(O(m^{2k-1})\).