A sparse Graham-Rothschild theorem

Prömel, Hans Jürgen; Voigt, Bernd

doi:10.1090/S0002-9947-1988-0957064-5

A sparse Graham-Rothschild theorem
HTML articles powered by AMS MathViewer

by Hans Jürgen Prömel and Bernd Voigt PDF

Trans. Amer. Math. Soc. 309 (1988), 113-137 Request permission

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

Gedenkrede auf Issai Schur

A restricted version of Hales-Jewett’s theorem

W. Deuber, B. L. Rothschild, and B. Voigt, Induced partition theorems, J. Combin. Theory Ser. A 32 (1982), no. 2, 225–240. MR 654623, DOI 10.1016/0097-3165(82)90022-X
W. Deuber and B. Voigt, Partitionseigenschaften endlicher affiner und projektiver Räume, European J. Combin. 3 (1982), no. 4, 329–340 (German, with English summary). MR 687731, DOI 10.1016/S0195-6698(82)80017-6
W. Deuber and B. Voigt, Der Satz von van der Waerden über arithmetische Progressionen, Jahresber. Deutsch. Math.-Verein. 85 (1983), no. 2, 66–85 (German). MR 698319
P. Frankl, R. L. Graham, and V. Rödl, Induced restricted Ramsey theorems for spaces, J. Combin. Theory Ser. A 44 (1987), no. 1, 120–128. MR 871393, DOI 10.1016/0097-3165(87)90064-1
R. L. Graham and B. L. Rothschild, Ramsey’s theorem for $n$-parameter sets, Trans. Amer. Math. Soc. 159 (1971), 257–292. MR 284352, DOI 10.1090/S0002-9947-1971-0284352-8
Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, Ramsey theory, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Inc., New York, 1980. MR 591457
A. W. Hales and R. I. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222–229. MR 143712, DOI 10.1090/S0002-9947-1963-0143712-1
Jaroslav Ne et il and Vojtěch Rödl, Van der Waerden theorem for sequences of integers not containing an arithmetic progression of $k$ terms, Comment. Math. Univ. Carolinae 17 (1976), no. 4, 675–681. MR 441906
Jaroslav Ne et il and Vojtěch Rödl, Another proof of the Folkman-Rado-Sanders theorem, J. Combin. Theory Ser. A 34 (1983), no. 1, 108–109. MR 685219, DOI 10.1016/0097-3165(83)90047-X
Jaroslav Ne et il and Vojtěch Rödl, Sparse Ramsey graphs, Combinatorica 4 (1984), no. 1, 71–78. MR 739415, DOI 10.1007/BF02579159
Jaroslav Ne et il and Vojtěch Rödl, On sets of integers with the Schur property, Graphs Combin. 2 (1986), no. 3, 269–275. MR 951571, DOI 10.1007/BF01788101
Jaroslav Ne et il and Vojtěch Rödl, Finite union theorem with restrictions, Graphs Combin. 2 (1986), no. 4, 357–361. MR 951561, DOI 10.1007/BF01788110
Hans Jürgen Prömel, Induced partition properties of combinatorial cubes, J. Combin. Theory Ser. A 39 (1985), no. 2, 177–208. MR 793270, DOI 10.1016/0097-3165(85)90036-6
Hans Jürgen Prömel, Partition properties of $q$-hypergraphs, J. Combin. Theory Ser. B 41 (1986), no. 3, 356–385. MR 864582, DOI 10.1016/0095-8956(86)90056-0
Hans J. Prömel and Bernd Voigt, Graham-Rothschild parameter sets, Mathematics of Ramsey theory, Algorithms Combin., vol. 5, Springer, Berlin, 1990, pp. 113–149. MR 1083597, DOI 10.1007/978-3-642-72905-8_{9}

Ramsey theorems for finite graphs

Richard Rado, Studien zur Kombinatorik, Math. Z. 36 (1933), no. 1, 424–470 (German). MR 1545354, DOI 10.1007/BF01188632

On Ramsey families of sets

Über die Kongruenz

25

Joel Spencer, Restricted Ramsey configurations, J. Combinatorial Theory Ser. A 19 (1975), no. 3, 278–286. MR 382058, DOI 10.1016/0097-3165(75)90053-9
Joel H. Spencer, Ramsey’s theorem for spaces, Trans. Amer. Math. Soc. 249 (1979), no. 2, 363–371. MR 525678, DOI 10.1090/S0002-9947-1979-0525678-7

Beweis einer Baudetschen Vermutung

15