Forbidden Submatrices: Some New Bounds and Constructions

  • R.P. Anstee
  • Ruiyuan Chen
Keywords: extremal set theory, forbidden submatrix, ordered sets, trace, amortized analysis


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.

Author Biographies

R.P. Anstee, Mathematics Department UBC

Professor of Mathemtics

Ph.D. Caltech 1980 (supervisor H.J. Ryser)

Ruiyuan Chen, Mathematics Department UBC



Article Number