The symmetry preserving removal lemma
HTML articles powered by AMS MathViewer
- by Balázs Szegedy PDF
- Proc. Amer. Math. Soc. 138 (2010), 405-408 Request permission
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(|A|^2)$. Then we can shrink each $S_i$ by $o(|A|)$ elements such that the new sets don’t have any arithmetic progression of the above type.References
- W. T. Gowers, Quasirandomness, counting and regularity for 3-uniform hypergraphs, Combin. Probab. Comput. 15 (2006), no. 1-2, 143–184. MR 2195580, DOI 10.1017/S0963548305007236
- B. Green, A Szemerédi-type regularity lemma in abelian groups, with applications, Geom. Funct. Anal. 15 (2005), no. 2, 340–376. MR 2153903, DOI 10.1007/s00039-005-0509-8
- Y. Ishigami, A Simple Regularization of Hypergraphs, arXiv:math/0612838v1
- Daniel Král, Oriol Serra, and Lluís Vena, A combinatorial proof of the removal lemma for groups, J. Combin. Theory Ser. A 116 (2009), no. 4, 971–978. MR 2513645, DOI 10.1016/j.jcta.2008.12.003
- Brendan Nagle, Vojtěch Rödl, and Mathias Schacht, The counting lemma for regular $k$-uniform hypergraphs, Random Structures Algorithms 28 (2006), no. 2, 113–179. MR 2198495, DOI 10.1002/rsa.20117
- Vojtěch Rödl and Jozef Skokan, Regularity lemma for $k$-uniform hypergraphs, Random Structures Algorithms 25 (2004), no. 1, 1–42. MR 2069663, DOI 10.1002/rsa.20017
- Vojtěch Rödl and Mathias Schacht, Regular partitions of hypergraphs: regularity lemmas, Combin. Probab. Comput. 16 (2007), no. 6, 833–885. MR 2351688, DOI 10.1017/s0963548307008553
- J. Solymosi, A note on a question of Erdős and Graham, Combin. Probab. Comput. 13 (2004), no. 2, 263–267. MR 2047239, DOI 10.1017/S0963548303005959
- E. Szemerédi, On sets of integers containing no $k$ elements in arithmetic progression, Acta Arith. 27 (1975), 199–245. MR 369312, DOI 10.4064/aa-27-1-199-245
- Terence Tao, A variant of the hypergraph removal lemma, J. Combin. Theory Ser. A 113 (2006), no. 7, 1257–1280. MR 2259060, DOI 10.1016/j.jcta.2005.11.006
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
- Received by editor(s): September 16, 2008
- Received by editor(s) in revised form: November 20, 2008
- Published electronically: October 14, 2009
- Communicated by: Jim Haglund
- © Copyright 2009
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 138 (2010), 405-408
- MSC (2000): Primary 05C99
- DOI: https://doi.org/10.1090/S0002-9939-09-09860-8
- MathSciNet review: 2557157