Spring 2017

Efficient Arithmetic Regularity and Removal Lemmas for Induced Bipartite Patterns

Tuesday, Jun. 19, 2018 10:15 am10:45 am

Add to Calendar

Let G be an abelian group of bounded exponent and A ? G . We show that if the collection of translates of A has bounded VC dimension , then for every ? > 0 there is a subgroup H of G of index at most poly(1/?) such that one can add or delete at most ?|G| elements to A to make it a union of H-cosets. We also establish a removal lemma with polynomial bounds, with applications to property testing, for induced bipartite patterns in a finite abelian group with bounded exponent. Joint work with Noga Alon and Jacob Fox.