General forbidden configuration theorems (Q1089344): Difference between revisions

Results in this paper gives bounds on the number of columns in a matrix when certain submatrices are forbidden. Let F be a k by \(\ell (0,1)\)- matrix with no repeated columns, column sums at least s. Let A be an m by n(0,1)-matrix with no repeated column, column sums at least s and no submatrix F nor any row and column permutation of F. Then \(n\leq \left( \begin{matrix} m\\ k-1\end{matrix} \right)+\left( \begin{matrix} m\\ k-2\end{matrix} \right)+...+\left( \begin{matrix} m\\ s\end{matrix} \right)\). This bound is best possible for numerous F. The bound, with \(s=0\), is an easy corollary to a bound of Sauer and Perles and Shelah. The bounds can be extended to any F and to any F where we do not allow row and column permutations. The results follow from a configuration theorem that says, in essence, that matrices without a configuration are determined by row intersections of sets of rows of various sizes. A linear independence argument yields the bound. Results of Ryser, Frankl and Pach, Quinn and the author are obtained.