The polynomial removal lemma conjecture for ordered binary matrices

A binary matrix is a matrix whose entries lie in {0,1}\{0,1\}. A copy of a k×kk\times k binary matrix AA in an n×nn\times n binary matrix MM consists of increasing row indices r1<<rkr_1<\dots<r_k and increasing column indices c1<<ckc_1<\dots<c_k such that

Mri,cj=Ai,j(1i,jk).M_{r_i,c_j}=A_{i,j}\qquad(1\leq i,j\leq k).

Ordered matrix removal conjecture. For every k×kk\times k binary matrix AA and every ε>0\varepsilon>0, there is a δ=δ(k,ε)=poly(ε)>0\delta=\delta(k,\varepsilon)=\operatorname{poly}(\varepsilon)>0 such that, whenever at least εn2\varepsilon n^2 entries of an n×nn\times n binary matrix MM must be changed to eliminate all copies of AA, the matrix MM contains at least

δn2k\delta n^{2k}

copies of AA. This is a central open problem for ordered matrices; the source notes that it is not known even for the 2×22\times2 identity matrix.

Sources & referencesView supporting material

Primary source

Lior Gishboliner and Asaf Shapira, “Polynomial Property Testing”, arXiv:2508.16878 (2025).

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.