Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

A sparse Graham-Rothschild theorem


Authors: Hans Jürgen Prömel and Bernd Voigt
Journal: Trans. Amer. Math. Soc. 309 (1988), 113-137
MSC: Primary 05A05
DOI: https://doi.org/10.1090/S0002-9947-1988-0957064-5
MathSciNet review: 957064
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The main result of this paper is a sparse version of the Graham-Rothschild partition theorem for $ n$-parameter sets [R. L. Graham and B. L. Rothschild, Ramsey's theorem for $ n$-parameter sets, Trans. Amer. Math. Soc. 159 (1971), 257-292]. In particular, a sparse version of Hales-Jewett's theorem is proved. We give several applications, e.g., for arithmetic progressions and finite sums of integers, confirming conjectures of J. Spencer and of J. Nešetřil and V. Rödl.

We also consider graphs defined on parameter sets and prove a sparse and restricted induced partition theorem for such graphs, extending results from [H. J. Prömel, Induced partition properties of combinatorial cubes, J. Combin. Theory Ser. A 39 (1985), 177-208] and [P. Frankl, R. L. Graham, and V. Rödl, Induced restricted Ramsey theorems for spaces, J. Combin. Theory Ser. A 44 (1987), 120-128].


References [Enhancements On Off] (What's this?)

  • [1973] A. Brauer, Gedenkrede auf Issai Schur, Issai Schur, Gesammelte Abhandlungen (A. Brauer and H. Rohrbach, eds.), Springer, Berlin, 1973, V-XIV.
  • [1984] W. Deuber, H. J. Prömel, B. L. Rothschild and B. Voigt, A restricted version of Hales-Jewett's theorem, Finite and Infinite Sets (A. Hajnal, L. Lovász and V. T. Sós, eds.), Colloq. Math. Soc. János Bolyai 37, North-Holland, Amsterdam, 1984, pp. 231-246.
  • [1982] W. Deuber, B. L. Rothschild and B. Voigt, Induced partition theorems, J. Combin. Theory Ser. A 32 (1982), 225-240. MR 654623 (83k:05013)
  • [1982] W. Deuber and B. Voigt, Partitionseigenschaften endlicher affiner und projektiver Räume, European J. Combin. 3 (1982), 329-340. MR 687731 (84c:05011)
  • [1983] -, Der Satz von van der Waerden über arithmetische Progressionen, Jber. Deutsch. Math.-Verein. 85 (1983), 66-85. MR 698319 (84j:10011)
  • [1987] P. Frankl, R. L. Graham and V. Rödl, Induced restricted Ramsey theorems for spaces, J. Combin. Theory Ser. A 44 (1987), 120-128. MR 871393 (88b:05013)
  • [1971] -, Ramsey's theorem for $ n$-parameter sets, Trans. Amer. Math. Soc. 159 (1971), 257-292. MR 0284352 (44:1580)
  • [1980] R. L. Graham, B. L. Rothschild and J. H. Spencer, Ramsey theory, Wiley, New York, 1980. MR 591457 (82b:05001)
  • [1963] A. W. Hales and R. I. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222-229. MR 0143712 (26:1265)
  • [1976] J. Nešetřil and V. Rödl, Van der Waerden's theorem for sequences of integers not containing an arithmetic progression of $ k$ terms, Comment. Math. Univ. Carolinae 17 (1976), 675-688. MR 0441906 (56:297)
  • [1983] -, Another proof of the Folkman-Rado-Sanders theorem, J. Combin. Theory Ser. A 34 (1983), 108-109. MR 685219 (84m:05058)
  • [1984] -, Sparse Ramsey graphs, Combinatorica 4 (1984), 71-78. MR 739415 (85h:05073)
  • [1986a] -, On sets of integers with the Schur property, Graphs and Combinatorics 2 (1986), 269-275. MR 951571 (89j:05016)
  • [1986b] -, Finite union theorem with restrictions, Graphs and Combinatorics 2 (1986), 357-361. MR 951561 (89i:05034)
  • [1985] H. J. Prömel, Induced partition properties of combinatorial cubes, J. Combin. Theory Ser. A 39 (1985), 177-208. MR 793270 (87g:05017)
  • [1986a] -, Partition properties of $ q$-hypergraphs, J. Combin. Theory Ser. B 41 (1986), 356-385. MR 864582 (88k:05143)
  • [1986] H. J. Prömel and B. Voigt, Graham Rothschild parameter sets, The Mathematics of Ramsey Theory (J. Nešetřil and V. Rödl, eds.), Springer-Verlag, Berlin, Heildberg and New York (to appear). MR 1083597
  • [1987] -, Ramsey theorems for finite graphs. I, Report No 86447-OR, Institut für Operations Research, Univ. Bonn, 1987.
  • [1933] R. Rado, Studien zur Kombinatorik, Math. Z. 36 (1933), 424-480. MR 1545354
  • [1981] V. Rödl, On Ramsey families of sets, unpublished manuscript.
  • [1986] -, Personal communication.
  • [xx] A. Rucinski and B. Voigt, in preparation.
  • [1917] I. Schur, Über die Kongruenz $ {x^m} + {y^m} = {z^m}\,(\bmod p)$, Jber. Deutsch. Math.-Verein. 25 (1917), 114-117.
  • [1975] J. Spencer, Restricted Ramsey configurations, J. Combin. Theory Ser. A 19 (1975), 278-286. MR 0382058 (52:2946)
  • [1979] -, Ramsey's theorem for spaces, Trans. Amer. Math. Soc. 249 (1979), 363-371. MR 525678 (80d:05008)
  • [1927] B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Arch. Wisk. 15 (1927), 212-216.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05A05

Retrieve articles in all journals with MSC: 05A05


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1988-0957064-5
Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society