Efficient arithmetic regularity and removal lemmas for induced bipartite patterns

DOI10.19086/DA.7757MaRDI QIDQ5211002zbMATH OpenOpenAlexFDO

Authors Noga Alon, Jacob Fox, Yufei Zhao

Publication date 17 January 2020

Published in discrete Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1801.04675

zbMATH Keywords

arithmetic regularityinduced patternsproperty testingregularity lemmaremoval lemmaVC dimension

Mathematics Subject Classification ID

Extremal set theory (05D05) Arithmetic combinatorics; higher degree uniformity (11B30)

Abstract: Let $G$ be an abelian group of bounded exponent and $AsubseteqG$. We show that if the collection of translates of $A$ has VC dimension at most $d$, then for every $epsilon>0$ there is a subgroup $H$ of $G$ of index at most $epsilo{n}^{-d-o(1)}$ such that one can add or delete at most $epsilon|G|$ 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.

Recommendations

• Induced arithmetic removal: complexity 1 patterns over finite fields
• Bounds for graph regularity and removal lemmas
• Arithmetic progressions, different regularity lemmas and removal lemmas
• Regularity lemmas and combinatorial algorithms
• Regularity Lemmas and Combinatorial Algorithms
• ARITHMETIC PROPERTIES OF -REGULAR BIPARTITIONS
• A polynomial bound for the arithmetic k-cycle removal lemma in vector spaces
• Algebraic characterizations of regularity properties in bipartite graphs
• Efficient enumeration of maximal induced bicliques
• A conjecture on bipartite graphical regular representations

Cited in

(14)

• Structure and regularity for subsets of groups with finite VC-dimension
• Induced arithmetic removal: complexity 1 patterns over finite fields
• Three-color Ramsey number of an odd cycle versus bipartite graphs with small bandwidth
• Convolutions of sets with bounded VC-dimension are uniformly continuous
• On finite sets of small tripling or small alternation in arbitrary groups
• Quantitative structure of stable sets in arbitrary finite groups
• NOTES ON THE STABLE REGULARITY LEMMA
• Quantitative structure of stable sets in finite abelian groups
• The coset and stability rings
• Approximate subgroups with bounded VC-dimension
• The VC dimension of quadratic residues in finite fields
• Is it easy to regularize a hypergraph with easy links?
• Finding certain arithmetic progressions in 2-coloured cyclic groups
• The VC-dimension of random subsets of finite groups

This page was built for publication: Efficient arithmetic regularity and removal lemmas for induced bipartite patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211002)