Small forbidden configurations. II (Q1593850)

Summary: The present paper continues the work begun by Anstee, Griggs and Sali on small forbidden configurations; see \textit{R. Antee, J. R. Griggs}, and \textit{A. Sali} [Graphs Comb. 13, No. 2, 97-118 (1997; Zbl 0878.05019)]. 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.