Polynomial dependence in ordered binary matrix removal

Open Problem: Better parameter dependence for ordered binary matrix removal · arXiv:1704.02367

arXiv Informal medium confidence— first stated 2017-04-07

Authors: Noga Alon, Omri Ben-Eliezer, Eldar Fischer

Status partial medium confidence

The open problem asks to improve the wowzer-type parameter dependence in the ordered binary matrix removal lemma (for finite families) to polynomial or at least exponential dependence between \delta^{-1} and \varepsilon^{-1}. Follow-up work has made partial progress: arXiv:2110.03577 characterises exactly when polynomial removal lemmas exist for ordered graphs (only for 2-vertex graphs or one specific 3-vertex configuration, up to symmetry), explicitly building on the Alon--Ben-Eliezer--Fischer framework and suggesting polynomial bounds for general families are rare; arXiv:2307.01652 proves a polynomial removal lemma for ordered matchings, a special subclass of ordered binary matrix patterns. The conjecture for arbitrary finite families of ordered binary matrices appears unresolved.

Cited literature (2)

partial Polynomial removal lemmas for ordered graphs (2021)

unknown · arXiv preprint · arXiv:2110.03577

Characterises exactly when \delta_F(\varepsilon) can be chosen polynomially for ordered-graph removal lemmas (only for |V(F)|=2 or one specific 3-vertex case), explicitly citing the Alon--Ben-Eliezer--Fischer result; implies polynomial bounds for general ordered binary matrix families are unlikely.
partial Polynomial removal lemma for ordered matchings (2023)

unknown · arXiv preprint · arXiv:2307.01652

Proves that for any ordered matching H on t vertices, an ordered n-vertex graph that is \varepsilon-far from H-free contains poly(\varepsilon)\cdot n^t copies of H, establishing a polynomial removal lemma for the ordered matching special case (a subclass of ordered binary matrices).

Reviewer notes. The paper arXiv:1609.04235 (Alon--Ben-Eliezer, submitted Sep 2016, journal 'Order' 2019) achieves polynomial dependence for a single forbidden ordered binary matrix; it predates the source paper and is therefore not listed in since_posted, but the source paper likely treats it as the starting point motivating the open problem for finite families. The two since_posted papers address ordered graphs and ordered matchings respectively -- closely related but not identical to ordered binary matrices in general. Author lists for arXiv:2110.03577 and arXiv:2307.01652 could not be confirmed from the abstract pages alone and are marked unknown.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. It will be interesting to combine the ideas from the current proof with the binary matrix regularity lemma of Alon, Fischer and Newman to obtain a removal lemma for finite families of ordered binary matrices with better dependence between the parameters $\delta^{-1}$ and $\varepsilon^{-1}$; ideally polynomial dependence, but even exponential dependence would be interesting.

Context

For ordered binary matrices, Alon, Fischer and Newman obtained an efficient conditional regularity lemma in which $\delta^{-1}$ is polynomial in $\varepsilon^{-1}$. The general ordered removal lemma proved in this paper inherits a wowzer-type dependence from the strong regularity lemma, and improving this for finite families of ordered binary matrices is posed as an open problem.

Notes. Stated as a research direction in Section 1.3 without a formal labelled environment.

Source paper

Testing hereditary properties of ordered graphs and matrices
Noga Alon, Omri Ben-Eliezer, Eldar Fischer · 2017-04-07
https://arxiv.org/abs/1704.02367 PDF source