Regularity-free ordered graph removal lemma

Open Problem: Regularity-free proof for the ordered removal lemma · 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 of finding a regularity-free proof of the ordered graph removal lemma (analogous to Fox's 2011 proof for unordered graphs) remains open in general. Partial progress has been made: the paper arXiv:2110.03577 characterizes exactly which ordered graphs F admit a polynomial bound on delta_F(epsilon) in the induced ordered removal lemma; and arXiv:2307.01652 proves a polynomial removal lemma for ordered matchings via a novel nested-partition technique that avoids the regularity lemma for that special case. A full regularity-free proof for arbitrary ordered graphs has not been found.

Cited literature (3)

partial Polynomial removal lemmas for ordered graphs (2021)

unknown · arXiv preprint · arXiv:2110.03577

Characterizes exactly which ordered graphs F admit a polynomial bound delta_F(epsilon) in the induced ordered removal lemma (if and only if |V(F)|=2 or F is a specific three-vertex ordered graph up to symmetry), giving a complete picture of when the wowzer-type dependence can be avoided.
partial Polynomial removal lemma for ordered matchings (2023)

unknown (includes Tomon) · arXiv preprint · arXiv:2307.01652

Proves a polynomial removal lemma for ordered matchings using a novel nested-partition cleaning argument that avoids the regularity lemma, achieving poly(epsilon) bounds for the special case of ordered matchings.
partial A Removal Lemma for Ordered Hypergraphs (2021)

Towsner, Henry · Proceedings of the London Mathematical Society · arXiv:2101.09769 · doi:10.1112/plms.70015

Generalizes the Alon-Ben-Eliezer-Fischer ordered graph removal lemma to induced ordered hypergraphs, but does not address the regularity-free question.

Reviewer notes. Fox's 2011 regularity-free proof for unordered graphs (arXiv:1006.1300) used entropy/energy-increment ideas. The analogous approach for ordered graphs remains open for general ordered graphs. arXiv:2307.01652 makes partial progress by proving polynomial bounds for ordered matchings via a regularity-free technique (nested partitions), and arXiv:2110.03577 characterizes the polynomial-bound regime for ordered graphs. Authors of 2110.03577 and 2307.01652 were not fully identified from available abstracts.

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

Informal. It will be interesting to try to obtain a proof for the ordered graph removal lemma that does not go through the strong regularity lemma needed in the current proof.

Context

The proofs of the ordered removal lemmas rely on strong variants of the graph regularity lemma, which impose a wowzer-type (tower-of-towers) dependence between the parameters $\delta^{-1}$ and $\varepsilon^{-1}$. Fox gave the first regularity-free proof of the unordered graph removal lemma, though still with tower-type dependence; an analogous approach for the ordered setting remains open.

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