Ordered binary matrix removal lemma

From papers

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.

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

No solutions have been posted yet.