Multivalued matrices and forbidden configurations

Abstract: An

r

-matrix is a matrix with symbols in

0, 1, l d o t s, r - 1

. A matrix is simple if it has no repeated columns. Let

c a l F

be a finite set of

r

-matrices. Let

h b o x f o r b (m, r, c a l 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 i n c a l F

. Many investigations have involved

r = 2

. For general

r

,

h b o x f o r b (m, r, c a l F)

is polynomial in

m

if and only if for every pair

i, j i n 0, 1, l d o t s, r - 1

there is a matrix in

c a l F

whose entries are only

i

or

j

. Let

{c a l T}_{e l l} (r)

denote the following

r

-matrices. For a pair

i, j i n 0, 1, l d o t s, r - 1

we form four

e l l i m e s e 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

h b o x f o r b (m, r, {c a l T}_{e l l} (r))

is a constant. Let

c a l F

be a finite set of 2-matrices. We ask if

is

T h e t a (h b o x f o r b (m, 2, c a l F))

and settle this in the affirmative for some cases including most 2-columned

F

.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Multivalued matrices and forbidden configurations