Efficient Arithmetic Regularity and Removal Lemmas for Induced Bipartite Patterns

被引：11

作者：

Alon, Noga ^{[1
,2
,3
]}

Fox, Jacob ^{[4
]}

Zhao, Yufei ^{[5
]}

机构：

[1] Tel Aviv Univ, Sch Math, IL-69978 Tel Aviv, Israel

[2] Tel Aviv Univ, Sch Comp Sci, IL-69978 Tel Aviv, Israel

[3] Princeton Univ, Dept Math, Princeton, NJ 08544 USA

[4] Stanford Univ, Dept Math, Stanford, CA 94305 USA

[5] MIT, Dept Math, Cambridge, MA 02139 USA

来源：

DISCRETE ANALYSIS | 2019年

关键词：

regularity lemma; removal lemma; property testing; VC dimension; arithmetic regularity; induced patterns; FREIMANS THEOREM; PROOF;

D O I：

10.19086/da.7757

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be an abelian group of bounded exponent and A subset of G. 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 epsilon(-d-o(1)) such that one can add or delete at most epsilon vertical bar G vertical bar 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.

引用

页数：14

共 32 条

[1] Efficient testing of bipartite graphs for forbidden induced subgraphs [J].