A Survey of Forbidden Configuration Results

Abstract

Let $F$ be a $k\times \ell$ (0,1)-matrix. We say a (0,1)-matrix $A$ has $F$ as a configuration if there is a submatrix of $A$ which is a row and column permutation of $F$. In the language of sets, a configuration is a trace and in the language of hypergraphs a configuration is a subhypergraph.

Let $F$ be a given $k\times \ell$ (0,1)-matrix. We define a matrix to be simple if it is a (0,1)-matrix with no repeated columns. The matrix $F$ need not be simple. We define $\hbox{forb}(m,F)$ as the maximum number of columns of any simple $m$-rowed matrix $A$ which do not contain $F$ as a configuration. Thus if $A$ is an $m\times n$ simple matrix which has no submatrix which is a row and column permutation of $F$ then $n\le\hbox{forb}(m,F)$. Or alternatively if $A$ is an $m\times (\hbox{forb}(m,F)+1)$ simple matrix then $A$ has a submatrix which is a row and column permutation of $F$. We call $F$ a forbidden configuration. 

The fundamental result is due to Sauer, Perles and Shelah, Vapnik and Chervonenkis. For $K_k$ denoting the $k\times 2^k$ submatrix of all (0,1)-columns on $k$ rows, then $\hbox{forb}(m,K_k)=\binom{m}{k-1}+\binom{m}{k-2}+\cdots \binom{m}{0}$. We seek asymptotic results for $\hbox{forb}(m,F)$ for a fixed $F$ and as $m$ tends to infinity . A conjecture of Anstee and Sali predicts the asymptotically best constructions from which to derive the asymptotics of $\hbox{forb}(m,F)$. The conjecture has helped guide the research and has been verified for $k\times \ell$ $F$ with $k=1,2,3$ and for simple $F$ with $k=4$ as well as other cases including $\ell=1,2$. We also seek exact values for $\hbox{forb}(m,F)$.