|
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
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 be an Abelian group with subsets such that the number of arithmetic progressions with is . Then we can shrink each by 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
-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
-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
-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
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.
|