Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Available in electronic format
Available in print format
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(e) ISSN 0002-9939(p)

     

The symmetry preserving removal lemma

Author(s): Balázs Szegedy
Journal: Proc. Amer. Math. Soc. 138 (2010), 405-408.
MSC (2000): Primary 05C99
Posted: October 14, 2009
MathSciNet review: 2557157
Retrieve article in: PDF

Abstract | References | Similar articles | Additional information

Abstract: In this paper we observe that in the hypergraph removal lemma, the edge removal can be done in such a way that the symmetries of the original hypergraph remain preserved. As an application we prove the following generalization of Szemerédi's Theorem on arithmetic progressions. Let $ A$ be an Abelian group with subsets $ S_1,S_2,\dots,S_t$ such that the number of arithmetic progressions $ x,x+d,\dots,x+(t-1)d$ with $ x+(i-1)d\in S_i$ is $ o(\vert A\vert^2)$. Then we can shrink each $ S_i$ by $ o(\vert A\vert)$ elements such that the new sets don't have any arithmetic progression of the above type.


References:

1.
T. Gowers, Quasirandomness, counting and regularity for $ 3$-uniform hypergraphs. Combin. Probab. Comput. 15 (2006), no. 1-2, 143-184. MR 2195580 (2008b:05175)

2.
B. Green, A Szemerédi type regularity lemma in Abelian groups, with applications, Geom. Funct. Anal. 15 (2005), no. 2, 340-376. MR 2153903 (2006e:11029)

3.
Y. Ishigami, A Simple Regularization of Hypergraphs, arXiv:math/0612838v1

4.
D. Král, O. Serra and L. Vena, A combinatorial proof of the removal lemma for groups, J. Combin. Theory Ser. A 116 (2009), 971-978. MR 2513645

5.
B. Nagle, V. Rödl and M. Schacht, The counting lemma for regular $ k$-uniform hypergraphs. Random Structures Algorithms 28 (2006), no. 2, 113-179. MR 2198495 (2007d:05084)

6.
V. Rödl and J. Skokan, Regularity lemma for $ k$-uniform hypergraphs. Random Structures Algorithms 25 (2004), no. 1, 1-42 MR 2069663 (2005d:05144)

7.
V. Rödl and M. Schacht, Regular partitions of hypergraphs: Regularity lemmas. Combin. Probab. Comput. 16 (2007), no. 6, 833-885. 42. MR 2351688 (2008h:05083)

8.
J. Solymosi, A note on a question of Erdős and Graham. Combin. Probab. Comput. 13 (2004), no. 2, 263-267. MR 2047239 (2004m:11012)

9.
E. Szemerédi, On sets of integers containing no $ k$ elements in arithmetic progression. Acta Arith. 27 (1975), 199-245. MR 0369312 (51:5547)

10.
T. Tao, A variant of the hypergraph removal lemma. J. Combin. Theory Ser. A 113 (2006), no. 7, 1257-1280. MR 2259060 (2007k:05098)


Similar Articles:

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 05C99

Retrieve articles in all Journals with MSC (2000): 05C99


Additional Information:

Balázs Szegedy
Affiliation: Department of Mathematics, University of Toronto, 40 St. George Street, Toronto, Ontario, M5S-2E4, Canada
Email: szegedyb@gmail.com

DOI: 10.1090/S0002-9939-09-09860-8
PII: S 0002-9939(09)09860-8
Received by editor(s): September 16, 2008,
Received by editor(s) in revised form: November 20, 2008
Posted: October 14, 2009
Communicated by: Jim Haglund
Copyright of article: Copyright 2009, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia