Avoiding patterns in matrices via a small number of changes

Abstract

Let $\mathcal{A}=\{A_1,\dots ,A_r\}$ be a partition of a set $\{1,\dots ,m\}\times \{1,\dots ,n\}$ into $r$ nonempty subsets, and $A=(a_{ij})$ be an $m\times n$ matrix. We say that $A$ has a pattern $\mathcal{A}$ provided that $a_{ij}=a_{i^{\prime }{j}^{\prime }}$ if and only if $(i,j),(i^{\prime },j^{\prime })\in A_t$ for some $t\in \{1,\dots ,r\}$. In this note we study the following function $f$ defined on the set of all $m\times n$ matrices $M$ with $s$ distinct entries: $f(M;\mathcal{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 $\mathcal{A}$. We give an asymptotically tight value for $$ f(m,n; s, {\cal A}) = \max\{f(M; {\cal A}): M \mbox{ is an } m\times n\mbox{ matrix with at most } s \mbox{ distinct entries}\} . $$

6 pages