Ordered binary matrix removal lemma
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Noga Alon, Omri Ben-Eliezer and Eldar Fischer, “Testing hereditary properties of ordered graphs and matrices”, arXiv:1704.02367 (2017).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.