The polynomial removal conjecture for ordered binary matrices

For a fixed binary $k\times k$ matrix $H$, an ordered copy in a binary $n\times n$ matrix $A$ is a choice of rows $r_1<\dots<r_k$ and columns $c_1<\dots<c_k$ with $A(r_i,c_j)=H(i,j)$, zeros included. Alon, Ben-Eliezer and Fischer proved qualitative ordered removal: if $A$ is $\epsilon$-far from $H$-free (at least $\epsilon n^2$ entry changes needed), it has at least $\delta(\epsilon)n^{2k}$ copies. Alon and Ben-Eliezer (Problem 1.4) asked whether $\delta$ can be polynomial, and Gishboliner and Shapira conjectured it for each single $H$. Are there $c_H,C_H>0$ with $N_H(A)\ge c_H\epsilon^{C_H}n^{2k}$ whenever $A$ is $\epsilon$-far from $H$-free?

Result

Disproved(see note)

Status

Candidate (review pending)

AI contribution

AI-discovered

Method

Construction

Field

Extremal combinatorics; property testing

Posed by

Noga Alon and Omri Ben-Eliezer (Problem 1.4, 2020); Lior Gishboliner and Asaf Shapira (Conjecture 4.5, 2025); question raised by Alon, Fischer and Newman (2007)

Year posed

2007

Years open

19y

Solved

2026-09-25

Model

Unreleased internal OpenAI model

Vendor

OpenAI

Collaborators

—

Verification

Lean-checked, statement unaudited

Publication

Announced

Collection

OpenAI math release (October 2026), version adc7f12

Significance

15 / 100*

Disclosed cost

—

Wikipedia

No dedicated article