Ordered binary matrix removal lemma

About 9 years old · traced to

Let an ordered binary matrix be a binary matrix whose rows and columns are equipped with orders. For a finite family F\mathcal{F} of ordered binary matrices, say that an n×nn \times n binary matrix is ϵ\epsilon-far from F\mathcal{F}-freeness if changing fewer than an ϵ\epsilon-fraction of its entries cannot make it free of every matrix in F\mathcal{F} as an ordered submatrix. If a member of F\mathcal{F} has dimensions a×ba \times b, let a copy mean an order-preserving occurrence of that matrix.

Ordered binary matrix removal lemma. For any finite family F\mathcal{F} of ordered binary matrices and any ϵ>0\epsilon > 0 there exists δ=δ(F,ϵ)\delta = \delta(\mathcal{F}, \epsilon) such that any n×nn \times n binary matrix which is ϵ\epsilon-far from F\mathcal{F}-freeness contains at least δna+b\delta n^{a+b} copies of some a×ba \times b matrix from F\mathcal{F}.

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

Never refreshed

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.