A survey of forbidden configuration results (Q1953538): Difference between revisions

Summary: Let \(F\) be a \(k\times l\) \((0,1)\)-matrix. We say a \((0,1)\)-matrix \(A\) has \(F\) as a configuration if there is a submatrix of \(A\) which is a row and column permutation of \(F\). In the language of sets, a configuration is a trace and in the language of hypergraphs a configuration is a subhypergraph. Let \(F\) be a given \(k\times l\) \((0,1)\)-matrix. We define a matrix to be simple if it is a \((0,1)\)-matrix with no repeated columns. The matrix \(F\) need not be simple. We define \(\operatorname{forb}(m,F)\) as the maximum number of columns of any simple \(m\)-rowed matrix \(A\) which do not contain \(F\) as a configuration. Thus if \(A\) is an \(m \times n\) simple matrix which has no submatrix which is a row and column permutation of \(F\) then \(n \leq \operatorname{forb}(m,F)\). Or alternatively if \(A\) is an \(m \times (\operatorname{forb}(m,F)+1)\) simple matrix then \(A\) has a submatrix which is a row and column permutation of \(F\). We call \(F\) a forbidden configuration. The fundamental result is due to Sauer, Perles and Shelah, Vapnik and Chervonenkis. For \(Kk\) denoting the \(k \times 2k\) submatrix of all \((0,1)\)-columns on \(k\) rows, then \(\operatorname{forb}(m,Kk) = (mk-1)+(mk-2)+ \dots (m0)\). We seek asymptotic results for \(\operatorname{forb}(m,F)\) for a fixed \(F\) and as m tends to infinity .A conjecture of \textit{R. P. Anstee} and \textit{A. Sali} [Combinatorica 25, No. 5, 503--518 (2005; Zbl 1107.05090)] predicts the asymptotically best constructions from which to derive the asymptotics of \(\operatorname{forb}(m,F)\). The conjecture has helped guide the research and has been verified for \(k \times l F\) with \(k=1,2,3\) and for simple \(F\) with \(k=4\) as well as other cases including \(l=1,2\). We also seek exact values for \(\operatorname{forb}(m,F)\).