Ordered binary matrix removal lemma
Let an ordered binary matrix be a binary matrix whose rows and columns are equipped with orders. For a finite family of ordered binary matrices, say that an binary matrix is -far from -freeness if changing fewer than an -fraction of its entries cannot make it free of every matrix in as an ordered submatrix. If a member of has dimensions , let a copy mean an order-preserving occurrence of that matrix.
Ordered binary matrix removal lemma. For any finite family of ordered binary matrices and any there exists such that any binary matrix which is -far from -freeness contains at least copies of some matrix from .
This conjecture asks whether the efficient conditional regularity lemma for ordered binary matrices yields a removal lemma analogous to the unordered binary-matrix result. The supplied text attributes the conjecture to Alon, Fischer and Newman; its resolution is not specified here.
References
Primary source
Noga Alon, Omri Ben-Eliezer and Eldar Fischer, “Testing hereditary properties of ordered graphs and matrices”, arXiv:1704.02367 (2017).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.