Small forbidden configurations. II
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.
- Geometric graphs with no self-intersecting path of length three
- Forbidden configurations: boundary cases
- Evidence for a forbidden configuration conjecture: One more case solved
- scientific article; zbMATH DE number 1978821 (Why is no real title available?)
- Design theory and some forbidden configurations
- Forbidden configurations and repeated induction
- Forbidden configurations and boundary cases
- Stability theorems for forbidden configurations
This page was built for publication: Small forbidden configurations. II
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1593850)
