An $r$-matrix is a matrix with symbols in $\{ 0,1,\ldots,r-1\}$. A matrix is simple if it has no repeated columns. Let ${ \cal F}$ be a finite set of $r$-matrices. Let $\hbox{ forb}(m,r,{ \cal F})$ denote the maximum number of columns possible in a simple $r$-matrix $A$ that has no submatrix which is a row and column permutation of any $F\in{ \cal F}$. Many investigations have involved $r=2$. For general $r$, $\hbox{ forb}(m,r,{ \cal F})$ is polynomial in $m$ if and only if for every pair $i,j\in\{ 0,1,\ldots,r-1\}$ there is a matrix in ${ \cal F}$ whose entries are only $i$ or $j$. Let ${ \cal T}_{ \ell}(r)$ denote the following $r$-matrices. For a pair $i,j\in\{ 0,1,\ldots,r-1\}$ we form four $\ell\times\ell$ matrices namely the matrix with $i$'s on the diagonal and $j$'s off the diagonal and the matrix with $i$'s on and above the diagonal and $j$'s below the diagonal and the two matrices with the roles of $i,j$ reversed. Anstee and Lu determined that $\hbox{ forb}(m,r,{ \cal T}_{ \ell}(r))$ is a constant. Let ${ \cal F}$ be a finite set of 2-matrices. We ask if $\hbox{ forb}(m,r,{ \cal T}_{ \ell}(3)\backslash { \cal T}_{ \ell}(2)\cup { \cal F})$ is $\Theta(\hbox{ forb}(m,2,{ \cal F}))$ and settle this in the affirmative for some cases including most 2-columned $F$.
Categories: math.CO