Multivalued matrices and forbidden configurations

Anstee, R.P. and Dawson, J. and Lu, L. and Sali, Attila (2023) Multivalued matrices and forbidden configurations. DISCRETE MATHEMATICS, 346 (9). ISSN 0012-365X

Preview

Text 1710.00374v1.pdf Download (227kB) | Preview

Abstract

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

Actions (login required)

Edit Item