Multivalued matrices and forbidden configurations

Abstract

An $r$-matrix is a matrix with symbols in $\{0,1,\dots ,r-1\}$. A matrix is simple if it has no repeated columns. Let $\mathcal{F}$ be a finite set of $r$-matrices. Let $forb(m,r,\mathcal{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 \mathcal{F}$. Many investigations have involved $r=2$. For general $r$, $forb(m,r,\mathcal{F})$ is polynomial in $m$ if and only if for every pair $i,j\in \{0,1,\dots ,r-1\}$ there is a matrix in $\mathcal{F}$ whose entries are only $i$ or $j$. Let ${\mathcal{T}}_{\ell }(r)$ denote the following $r$-matrices. For a pair $i,j\in \{0,1,\dots ,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 $forb(m,r,{\mathcal{T}}_{\ell }(r))$ is a constant. Let $\mathcal{F}$ be a finite set of 2-matrices. We ask if $forb(m,r,{\mathcal{T}}_{\ell }(3)\backslash {\mathcal{T}}_{\ell }(2)\cup \mathcal{F})$ is $\Theta (forb(m,2,\mathcal{F}))$ and settle this in the affirmative for some cases including most 2-columned $F$.