Efficient Arithmetic Regularity and Removal Lemmas for Induced Bipartite Patterns

Noga Alon, Jacob Fox, Yufei Zhao

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


Let G be an abelian group of bounded exponent and A ⊆ G. We show that if the collection of translates of A has VC dimension at most d, then for every ε > 0 there is a subgroup H of G of index at most ε-d-o(1) such that one can add or delete at most ejGj elements to/from 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

Original languageEnglish (US)
Article number3
JournalDiscrete Analysis
StatePublished - 2019

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


  • Arithmetic regularity
  • Induced patterns
  • Property testing
  • Regularity lemma
  • Removal lemma
  • Vc dimension


Dive into the research topics of 'Efficient Arithmetic Regularity and Removal Lemmas for Induced Bipartite Patterns'. Together they form a unique fingerprint.

Cite this