Download PDF - Arithmetic progressions of length three in subsets of a random setAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Arithmetic progressions of length three in subsets of a random set

Authors 1, 2, 3, 3

Affiliations

  1. Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508-900 São Paulo, SP, Brazil
  2. Department of Mathematics and Computer Science, Adam Mickiewicz University, Matejki 48/49, 60-769 Poznań, Poland
  3. Department of Mathematics and Computer Science, Emory University, Atlanta, Georgia 30322, U.S.A.

Keywords

ENG
Szemerédi's theorem, arithmetic progressions, combinatorial number theory, regularity lemma, random sets of integers

Bibliography

  1. [ADLRY 94] N. Alon, R. A. Duke, H. Lefmann, V. Rödl and R. Yuster, The algorithmic aspects of the regularity lemma, J. Algorithms 16 (1994), 80-109.
  2. [EFR 86] P. Erdős, P. Frankl and V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs Combin. 2 (1986), 113-121.
  3. [ET 36] P. Erdős and P. Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261-264.
  4. [FRW 88] P. Frankl, V. Rödl and R. Wilson, The number of submatrices of a given type in a Hadamard matrix and related results, J. Combin. Theory Ser. B 44 (1988), 317-328.
  5. [Fu 77] H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. Anal. Math. 31 (1977), 204-256.
  6. [GN 86] R. L. Graham and J. Nešetřil, Large minimal sets which force long arithmetic progressions, J. Combin. Theory Ser. A 42 (1986), 270-276.
  7. [GR 87] R. L. Graham and V. Rödl, Numbers in Ramsey theory, in: Surveys in Combinatorics 1987, C. Whitehead (ed.), London Math. Soc. Lecture Note Ser. 123, Cambridge University Press, Cambridge, 1987, 111-153.
  8. [HKŁ 95] P. E. Haxell, Y. Kohayakawa and T. Łuczak, The induced size-Ramsey number of cycles, Combin. Probab. Comput. 4 (1995), 217-239.
  9. [H-B 87] D. R. Heath-Brown, Integer sets containing no arithmetic progressions, J. London Math. Soc. 35 (1987), 385-394.
  10. [JŁR 90] S. Janson, T. Łuczak and A. Ruciński, An exponential bound for the probability of nonexistence of a specified subgraph in a random graph, in: Random Graphs '87, M. Karoński, J. Jaworski and A. Ruciński (eds.), Wiley, 1990, 73-87.
  11. [McD 89] C. J. H. McDiarmid, On the method of bounded differences, in: Surveys in Combinatorics 1989, J. Siemons (ed.), London Math. Soc. Lecture Note Ser. 141, Cambridge University Press, Cambridge, 1989, 148-188.
  12. [NR 87] J. Nešetřil and V. Rödl, Partite construction and Ramseyan theorems for sets, numbers and spaces, Comment. Math. Univ. Carolin. 28 (1987), 569-580.
  13. [PV 88] H.-J. Prömel and B. Voigt, A sparse Graham-Rothschild theorem, Trans. Amer. Math. Soc. 309 (1988), 113-137.
  14. [Rö 90] V. Rödl, On Ramsey families of sets, Graphs Combin. 6 (1990), 187-195.
  15. [Ro 53] K. F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 104-109.
  16. [RSz 78] I. Z. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, Colloq. Math. Soc. János Bolyai 18 (1978), 939-945.
  17. [Sp 75] J. Spencer, Restricted Ramsey configurations, J. Combin. Theory Ser. A 19 (1975), 278-286.
  18. [Sz 75] E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975), 299-345.
  19. [Sz 78] E. Szemerédi, Regular partitions of graphs, in: Problèmes Combinatoires et Théorie des Graphes, Proc. Colloque Inter. CNRS, J.-C. Bermond, J.-C. Fournier, M. Las Vergnas et D. Sotteau (eds.), CNRS, Paris, 1978, 399-401.
  20. [Th 87a] A. Thomason, Pseudo-random graphs, in: Random Graphs '85, M. Karoński and Z. Palka (eds.), Ann. Discrete Math. 33, North-Holland, Amsterdam, 1987, 307-331.
  21. [Th 87b] A. Thomason, Random graphs, strongly regular graphs and pseudo-random graphs, in: Surveys in Combinatorics 1987, C. Whitehead (ed.), London Math. Soc. Lecture Note Ser. 123, Cambridge University Press, Cambridge, 1987, 173-195.
Acta Arithmetica
1996/75/2
Export to PBN, Opens in new tab
Pages:
133-163
Main language of publication
English
Received
1995-06-09
Published
1996
Exact and natural sciences