2016/09/14 by Noga Alon, Alon, Noga, Omri Ben-Eliezer +1 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1609.04235
To appear in RANDOM 2017
arxiv created 2017/06/12 · arxiv updated 2017/06/14
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.