Combinatorial Theory

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 \(\varepsilon›0\), then there exists \(\delta_{F}(\varepsilon)›0\) such that every \(n\)-vertex ordered graph \(G\) containing at most \(\delta_{F}(\varepsilon) n^{v(F)}\) induced copies of \(F\) can be made induced \(F\)-free by adding/deleting at most \(\varepsilon n^2\) edges. We prove that \(\delta_{F}(\varepsilon)\) can be chosen to be a polynomial function of \(\varepsilon\) 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.

Mathematics Subject Classifications: 05C35, 05C75

Keywords: Ordered graph, removal lemma