Arithmetic Progressions, Different Regularity Lemmas and Removal Lemmas

Abstract

This lecture note is mainly about arithmetic progressions, different regularity lemmas and removal lemmas. We will be very brief most of the time, trying to avoid technical details, even definitions. For most technical details, we refer the reader to references. Apart from arithmetic progressions, we also discuss property testing and extremal graph theory.

Keywords

Arithmetic progressions / Regularity lemmas / Removal lemmas

References

[1] Alon N, Fischer E, Krivelevich M, Szegedy M. Efficient testing of large graphs. Combinatorica. 2000, 20 451-476

[2] Bergelson V, Leibman A. Polynomial extensions of van der Waerden’s and Szemerédi theorems. J. Am. Math. Soc.. 1996, 9 725-753

[3] Bourgain J. On triples in arithmetic progression. GAFA. 1999, 9 5 968-984

[4] Bollobás B, Erdős P. On a Ramsey-Turán type problem. J. Comb. Theory Ser. B. 1976, 21 2 166-168

[5] Bollobás, B., Erdős, P., Simonovits, M.: On the structure of edge graphs. II. J. London Math. Soc. (2) 12(2), 219–224 (1975/76)

[6] Conlon, D., Fox, J., Zhao, Y.: Extremal results in sparse pseudorandom graphs, Submitted

[7] Elek G, Szegedy B. A measure-theoretic approach to the theory of dense hypergraphs. Ad. Math.. 2012, 231 3–4 1731-1772

[8] Frankl P, Rödl V. Extremal problems on set systems. Random Struct. Algorithm. 2002, 20 131-164

[9] Frieze, A., Kannan, R.: The regularity lemma and approximation schemes for dense problems, Proceedings of the 37th IEEE FOCS 12–20 (1996)

[10] Furstenberg H. Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions. J. Anal. Math.. 1977, 31 204-256

[11] Furstenberg H, Katznelson Y. A density version of the Hales–Jewett theorem. J. Anal. Math.. 1991, 57 64-119

[12] Furstenberg H, Katznelson Y. An ergodic Szemerédi theorem for commuting transformations. J. Anal. Math.. 1978, 34 275-291

[13] Gowers WT. A new proof of Szemerédi’s Theorem. Geom. Funct. Anal.. 2001, 11 465-588

[14] Gowers WT. Hypergraph regularity and the multidimensional Szemerédi theorem. Ann. Math.. 2007, 166 897-946

[15] Green B, Tao T. The primes contain arbitrarily long arithmetic progressions. Ann. Math.. 2008, 167 481-547

[16] Green, B., Tao, T.: New bounds for Szemeredi’s Theorem, II, Analytic number theory: essays in honour of Klaus Roth, W. W. L. Chen, W. T. Gowers, H. Halberstam, W. M. Schmidt, R. C. Vaughan, eds, Cambridge University Press, Cambridge University 180–204 (2009)

[17] Green, B., Tao, T.: New bounds for Szemeredi’s Theorem, III, preprint

[18] Green B, Tao T, Ziegler T. An inverse theorem for the Gowers $U^{s+1}[N]$ norm. Ann. Math.. 2012, 176 2 1231-1372

[19] Goldreich O, Goldwasser S, Ron D. Property testing and its applications to learning and approximation. J. ACM. 1998, 45 653-750

[20] Heath-Brown DR. Integer sets containing no arithmetic progressions. J. Lond. Math. Soc.. 1987, 35 385-394

[21] Nagle B, Rödl V, Schacht M. The counting lemma for regular k-uniform hypergraphs. Random Struct. Algorithm.. 2006, 28 113-179

[22] Rödl V, Skokan J. Regularity lemma for uniform hypergraphs. Random Struct. Algorithm.. 2004, 25 1-42

[23] Roth KF. On certain sets of integers. J. Lond. Math. Soc.. 1953, 28 104-109

[24] Rubinfield R, Sudan M. Robust characterization of polynomials with applications to program testing. SIAM J. Comput.. 1996, 25 252-271

[25] Ruzsa, I.Z., Szemerédi, E.: Triple systems with no six points carrying three triangles. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, pp. 939–945, Colloq. Math. Soc. Janos Bolyai, 18, North-Holland, Amsterdam-New York, (1978)

[26] Sanders T. On Roths theorem on progressions. Ann. Math.. 2011, 174 619-634

[27] Solymosi, J.: Note on a generalization of Roth’s theorem, in Discrete and computational geometry, Algorithms Combin. Vol. 25, Springer, New York 825–827 (2003)

[28] Szegedy, B.: On higher order fourier analysis. arXiv:1203.2260

[29] Szemerédi E. On sets of integers containing no four elements in arithmetic progression. Acta Math. Acad. Sci. Hung.. 1969, 20 89-104

[30] Szemerédi E. Integer sets containing no k elements in arithmetic progression. Acta Arith.. 1975, 27 299-345

[31] Szemerédi, E.: Regular partitions of graphs, in Colloques Internationaux CNRS 260 - Problemes Combinatoires et Theorie des Graphes, Orsay, 399–401, (1976)

[32] Szemerédi, E.: On graphs containing no complete subgraph with 4 vertices. (Hungarian) Mat. Lapok 23 (1972), 113–116 (1973)

[33] Szemerédi E. Integer sets containing no arithmetic progressions. Acta Math. Hungar.. 1990, 56 1–2 155-158

[34] Tao T, Ziegler T. The inverse conjecture for the Gowers norm over finite fields in low characteristic. Ann. Comb.. 2012, 16 1 121-188