Efficient removal lemmas for matrices

The authors and Fischer recently proved that any hereditary property of two-dimensional matrices (where the row and column order is not ignored) over a finite alphabet is testable with a constant number of queries, by establishing the following (ordered) matrix removal lemma: For any finite alphabet Σ, any hereditary property P of matrices over Σ, and any ϵ > 0, there exists fP(ϵ) such that for any matrix M over Σ that is ϵ-far from satisfying P, most of the fP(ϵ) × fP(ϵ) submatrices of M do not satisfy P. Here being ϵ-far from P means that one needs to modify at least an ϵ-fraction of the entries of M to make it satisfy P. However, in the above general removal lemma, fP(ϵ) grows very fast as a function of ϵ-1, even when P is characterized by a single forbidden submatrix. In this work we establish much more efficient removal lemmas for several special cases of the above problem. In particular, we show the following: For any fixed s×t binary matrix A and any ϵ > 0 there exists δ > 0 polynomial in ϵ, such that for any binary matrix M in which less than a δ-fraction of the s×t submatrices are equal to A, there exists a set of less than an ϵ-fraction of the entries of M that intersects every A-copy in M. We generalize the work of Alon, Fischer and Newman [SICOMP'07] and make progress towards proving one of their conjectures. The proofs combine their efficient conditional regularity lemma for matrices with additional combinatorial and probabilistic ideas.