Linear algebra methods for Forbidden configurations (Q653981): Difference between revisions

A matrix is called simple if it is a \((0,1)\) matrix with no repeated columns. Let \(F\) be a \(k\times n\) \((0,1)\) matrix, and let forb\((m,F)\) stand for the largest number of columns in an \(m\)-rowed simple matrix for which no \(k\times n\) submatrix is a row and column permutation of \(F.\) It has been shown that if \(F\) is a \(k\)-rowed matrix then forb\((m,F)\) is \(O(m^{k}).\) In the paper all \(k\)-rowed matrices \(F\) for which forb\((m,F)\) is \(O(m^{k-1})\) and for which forb\((m,F)\) is \(\Theta (m^{k})\) are characterized.