The ordered matrix removal conjecture asks for polynomial quantitative bounds when eliminating a fixed binary matrix pattern from a larger binary matrix. For a fixed pattern , a copy in an matrix uses increasing row indices and increasing column indices, independently, and matches every zero and one of . Write for the number of these copies. The matrix is -far from -free if at least entries must be changed to eliminate every copy. The conjectural estimate has the form

with positive constants depending only on .

See also

Matrix, Submatrix

Explore with Wolfram|Alpha

References

Alon, N. and Ben-Eliezer, O. "Efficient Removal Lemmas for Matrices." Order 37, 83-101, 2020. https://doi.org/10.1007/s11083-019-09494-3.

Cite this as:

Weisstein, Eric W. "Ordered Matrix Removal Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/OrderedMatrixRemovalConjecture.html

Subject classifications