Small forbidden configurations. II
type: Item
instance of: scholarly article
title: Small forbidden configurations. II
zbMATH Open document ID: 0960.05100
author: Ron Ferguson
author: Attila Sali
author: R. P. Anstee
published in: The Electronic Journal of Combinatorics
publication date: 2001-02-08T00:00:00Z
full work available at URL: https://eudml.org/doc/120921
full work available at URL: v8i1r4.html
review text: 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.
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C90
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 05B30
zbMATH DE Number: 1557042
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1557042