Abstract
Addressing a problem of Goldreich and of Alon and Fox, we prove new sufficient and necessary criteria, guaranteeing that a graph property admits a removal lemma with a polynomial bound. Although both are simple combinatorial criteria, they imply almost all prior positive and negative results of this type, as well as many new ones. In particular, we will show that every semi-algebraic graph property admits a removal lemma with a polynomial bound. This confirms a conjecture of Alon.
Joint work with L. Gishboliner