Small Forbidden Configurations II

Abstract

The present paper continues the work begun by Anstee, Griggs and Sali on small forbidden configurations. In the notation of (0,1)-matrices, we consider a (0,1)-matrix $F$ (the forbidden configuration), an $m\times n$ (0,1)-matrix $A$ with no repeated columns which has no submatrix which is a row and column permutation of $F$, and seek bounds on $n$ in terms of $m$ and $F$. We give new exact bounds for some $2\times l$ forbidden configurations and some asymptotically exact bounds for some other $2\times l$ forbidden configurations. We frequently employ graph theory and in one case develop a new vertex ordering for directed graphs that generalizes Rédei's Theorem for Tournaments. One can now imagine that exact bounds could be available for all $2\times l$ forbidden configurations. Some progress is reported for $3\times l$ forbidden configurations. These bounds are improvements of the general bounds obtained by Sauer, Perles and Shelah, Vapnik and Chervonenkis.