Efficient Arithmetic Regularity and Removal Lemmas for Induced Bipartite Patterns

Noga Alon, Jacob Fox, Yufei Zhao

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

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.

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

All Science Journal Classification (ASJC) codes

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

Keywords

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

Fingerprint

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

Cite this