TOPICS
Search

Ordered Matrix Removal Conjecture


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 k×k pattern H, a copy in an n×n matrix A uses increasing row indices and increasing column indices, independently, and matches every zero and one of H. Write N_H(A) for the number of these copies. The matrix is epsilon-far from H-free if at least epsilonn^2 entries must be changed to eliminate every copy. The conjectural estimate has the form

 N_H(A)>=c_Hepsilon^(C_H)n^(2k),

with positive constants depending only on H.


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