Talks
Spring 2017

Removal Lemmas with Polynomial Bounds

Tuesday, March 7th, 2017 9:30 am10:30 am

Add to Calendar

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