Polynomial removal lemmas for ordered graphs

Abstract

A recent result of Alon, Ben-Eliezer and Fischer establishes an induced removal lemma for ordered graphs. That is, if $F$ is an ordered graph and $\epsilon >0$, then there exists ${\delta }_F(\epsilon )>0$ such that every $n$-vertex ordered graph $G$ containing at most ${\delta }_F(\epsilon )n^{v(F)}$ induced copies of $F$ can be made induced $F$-free by adding/deleting at most $\epsilon n^2$ edges. We prove that ${\delta }_F(\epsilon )$ can be chosen to be a polynomial function of $\epsilon$ if and only if $|V(F)|=2$, or $F$ is the ordered graph with vertices $x<y<z$ and edges $\{x,y\},\{x,z\}$ (up to complementation and reversing the vertex order). We also discuss similar problems in the non-induced case.