Avoiding Patterns in Matrices Via a Small Number of Changes

Abstract: Let

c a l A = A_{1}, l d o t s, A_{r}

be a partition of a set

1, l d o t s, m i m e s 1, l d o t s, n

into

r

nonempty subsets, and

A = (a_{i j})

be an

m i m e s n

matrix. We say that

A

has a pattern

c a l A

provided that

a_{i j} = a_{i^{'} j^{'}}

if and only if

(i, j), (i^{'}, j^{'}) i n A_{t}

for some

t i n 1, l d o t s, r

. In this note we study the following function

f

defined on the set of all

m i m e s n

matrices

M

with

s

distinct entries:

f (M; c a l A)

is the smallest number of positions where the entries of

M

need to be changed such that the resulting matrix does not have any submatrix with pattern

c a l A

. We give an asymptotically tight value for

f(m,n; s, {cal A}) = max{f(M; {cal A}): M mbox{ is an } m imes nmbox{ matrix with at most } s mbox{ distinct entries}} .

Recommendations

Cited in

(5)

This page was built for publication: Avoiding Patterns in Matrices Via a Small Number of Changes