2017/10/01 by Richard Anstee, Jeffrey Dawson, Anstee, Richard +5
Mathematics · #05D05 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05D05
paper · pdf · doi:10.48550/arxiv.1710.00374
arxiv created 2017/10/01 · arxiv updated 2017/10/03
An r-matrix is a matrix with symbols in \0,1,…,r-1\. A matrix is simple if it has no repeated columns. Let \cal F be a finite set of r-matrices. Let \hboxforb(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∈\cal F. Many investigations have involved r=2. For general r, \hboxforb(m,r,\cal F) is polynomial in m if and only if for every pair i,j∈\0,1,…,r-1\ there is a matrix in \cal F whose entries are only i or j. Let \cal Tℓ(r) denote the following r-matrices. For a pair i,j∈\0,1,…,r-1\ we form four ℓ×ℓ 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 \hboxforb(m,r,\cal Tℓ(r)) is a constant. Let \cal F be a finite set of 2-matrices. We ask if \hboxforb(m,r,\cal Tℓ(3)\backslash \cal Tℓ(2)∪ \cal F) is Θ(\hboxforb(m,2,\cal F)) and settle this in the affirmative for some cases including most 2-columned F.