Forbidden submatrices: some new bounds and constructions (Q1953376)

Summary: We explore an extremal hypergraph problem for which both the vertices and edges are ordered. Given a hypergraph \(F\) (not necessarily simple), we consider how many edges a simple hypergraph (no repeated edges) on \(m\) vertices can have while forbidding \(F\) as a subhypergraph where both hypergraphs have fixed vertex and edge orderings. A hypergraph of \(n\) edges on \(m\) vertices can be encoded as an \(m\times n\) \((0,1)\)-matrix. We say a matrix is simple if it is a (0,1)-matrix with no repeated columns. Given a (0,1)-matrix \(F\), we define \({\hbox{fs}}(m,F)\) as the maximum, over all simple matrices \(A\) which do not have \(F\) as a submatrix, of the number of columns in \(A\). The row and column order matter. It is known that if \(F\) is \(k\times \ell\) then \({\hbox{fs}}(m,F)\) is \(O(m^{2k-1-\epsilon})\) where \(\epsilon=(k-1)/(13\log_2 \ell)\). Anstee, Frankl, Füredi and Pach have conjectured that if \(F\) is \(k\)-rowed, then \({\hbox{fs}}(m,F)\) is \(O(m^k)\). We show \({\hbox{fs}}(m,F)\) is \(O(m^2)\) for \(F= \left[{1\,0\,1\,0\,1\atop 0\,1\,0\,1\,0}\cdots\right]\) and for \(F= \left[{1\,0\,1\,0\,1\atop 1\,0\,1\,0\,1}\cdots\right]\). The proofs use a type of amortized analysis. We also give some constructions.