Small forbidden configurations. IV: The 3 rowed case (Q2368585)

This paper is a continuation of a series of previous works on forbidden patterns in simple matrices. A \((0,1)\)-matrix with no repeated columns is called a simple matrix. A \(k\) by \(l\) matrix \(F\) is a configuration in \(A\), if \(A\) has a submatrix which is a row and column permutation of \(F\). For a fixed \(m\) and a configuration \(F\) we denote by forb(\(m,F\)) the largest \(n\) such that there exists an \(n\) by \(m\) simple matrix \(A\) without the configuration \(F\) (forbidden configuration). The paper presents forb(\(m,F\)) for \(3\)-row matrices \(F\). This function is either \(\Theta(m)\), \(\Theta(m^2)\) or \(\Theta(m^3)\) depending on the structure of \(F\).